CTRL+A, for example, is printing "^A" instead of returning my cursor to the start of the line.
This happens via ssh, in a screen session, or on the hard console. $TERM shows either xterm or linux depending on which one I'm on.
How do I get the keymap fixed?
You have enabled vi mode for bash somewhere like this "set -o vi" (probably in your ~/.bashrc file)
You need to remove that line or change to "set -o emacs"