While you could run a Python web framework on top of CGI, I don't think you want to: a web framework provides you with lots of extra functionality to make your coding easier, but part of the price you pay for that is that the framework has lots of extra code to supply that functionality -- that code needs to get loaded, and its initialization parts executed, every time your web application process starts.
CGI starts a fresh process for your code every time the corresponding URL gets visited, and that process terminates when it's done responding to that single visit. So, you really want to do as little initialization work as possible, to avoid responding very slowly to user requests.
So, if all your hosting provider allows you is CGI, you probably want to program "down to the bare CGI interface", in order to minimize the start-up/shut-down overhead.
You can get a good overview of the issues and possibilities in Marek Kubica's howto "HOWTO Use Python in the web". WSGI (among many other ways it can interface to the underlying web server) can run on top of CGI, so in theory you can use any Python web framework which supports WSGI (which means just about all modern ones) -- the point is, unless you're doing nothing more than just learning and "playing around", you don't want to incur that startup overhead over and over again on pages you're actually serving. (If you are just learning and playing around, you can run a web server on your own machine for your own exclusive use, so your hosting provider's limitations are irrelevant;-).
If you do decide to program at "bare CGI" level, you can start at this page -- make sure you follow the various links from it to useful tutorials and to the voidspace collection of useful and interesting examples of Python CGI scripts.
For a survey of some of the many available Python web app frameworks, you can start here
where for each framework covered you'll find some information and links.
Last but not least, you should not ignore the possibility of developing web apps on Google App Engine -- albeit with its own peculiarities and limitations, it does offer a WSGI-compliant environment that is free of charge for even pretty intense usage. There are interesting lightweight frameworks developed specifically to take advantage of App Engine, such as the excellent tipfy (this page from the tipfy wiki also links to others), but in particular you can run the popular django framework there (with peculiarities and limitations, as I said -- in particular, no relational database underneath -- but it's still the most popular choice despite that).
In App Engine's early days some people were worried that using it could lead to "lock in" -- since it's different from other hosting environments, wouldn't web apps developed for it be hard to port elsewhere if and when one wanted to? Fortunately, open-source software like appscale and typhoonae has dispelled any such worries.