This guy had it figured out: http://www.vertigrated.com/blog/2010/02/python-remote-ssh-with-paramiko/
You just have to send multiple commands with one exec_command, such as:
myssh.exec_command('cd ..; pwd')
Then stdout.readlines() will return the directory that you changed to.