I don't know how I ever missed this Apple Mail plugin, but you absolutely have to give MsgFiler a try if you're a heavy keyboard user. It lets you move messages into any folder in your mailbox using only the keyboard.
Press ⌘9 to pull up a TextMate-like list of your mailbox folders. Then, select a folder by typing the first few letters in its name and move the currently selected message(s) into it with ↩.
You can also jump to a folder with ⌘O instead of ↩. Awesome.