I'm being trying to 

Log into a server using SHH (with Paramiko)
Use that connection like a proxy and route network traffic through it and out to the internet. So say I could set it as my proxy in Urllib2, Mechanize, Firefox, etc.).

Is the second part possible or will I have to have some sort of proxy server running on the server to get this to work?
You could implement a SOCKS proxy in the paramiko client that routes connections across the SSH tunnel via paramiko's open_channel method.  Unfortunately, I don't know of any out-of-the-box solution that does this, so you'd have to roll your own.  Alternatively, run a SOCKS server on the server, and just forward that single port via paramiko.
Python Proxy Through SSH