I'm currently using sup (http://sup.rubyforge.org/), which has labels and threads like Gmail, but is Free as in Freedom, runs on ncurses and, ironically, has a much better search mechanism, which was the main reason I switched from Gmail. There is also notmuch (http://notmuchmail.org/), which is still alpha, but aims to be faster and more scriptable than Sup.