Level 1
If you look at the python documentation, they cover some of the historical methods of web programming [1]. They explain that there are many ways to write (and run) python programs on the server. Historically the first was CGI, but this is typically the slowest, most inconvenient, and the most insecure method (not inherently insecure but because it is easy to shoot yourself in the foot). More commonly, now there are *web frameworks* that help you to handle the things common in web programming such as handling form data, headers, etc... The most popular examples of Python web frameworks are Django, TurboGears, Web.py, Flask etc..All of the above requires a front facing web server (such as Apache or Nginx) that passes requests to some Python based backend. This is ideal for industrial strength applications but for simpler projects people began realizing: "If I am going to be writing my entire application in Python anyway, then why do I need a server in front of my application at all? So some people have written python *servers* such as CherryPy and Tornado that are very simple to use (especially CherryPy), and are often great for really simple use cases as you don't have to be running anything besides your Python code directly, which serves up it's own HTTP goodness.
Level 2
Now, how to host these applications? First came shared hosting, such as most GoDaddy hosting and the like. These allow you limited use of CGI scripts (or maybe some of the newer replacements of CGI such as FastCGI, WSGI, etc..) but you don't have full control of the system.However, the CGIs are rather low level interfaces (making you handle everything yourself), so Google (and others like Microsoft and Heroku) started making *Platforms* on which you can build dynamic web applications more easily. Google App Engine is the most famous [2] and [3], and allows you to run small apps, written in python, for free! The only problem is, there are limitations on what python packages you can use (most common the problem is: No matplotlib and no numpy/scipy (because they have binary parts to them). But if that's not a problem then you should definitely look into Google App Engine (thats what my personal site runs on for example). They have a lot of great documentation you can read.
Update: I recently noticed that the new Python 2.7 backend for Google App Engine has support for some limited libraries such as PIL (for image manipulation) and Numpy for fast numeric vector manipulation. This is a great addition to the service, but you will always want 'one more library', so please keep that in mind.
Level 3
Now the final level of questioning is: what are you going to be doing with your code? The reason I ask, is that there has been an enormous movement lately to push everything from the server side to the client side. Meaning: rather than write all the code to run on the server, run it all in Javascript in order to run it directly in the users browser.This may sound strange: "Why would they do this?" you may ask and there are many wonderful reasons that I won't go into here. But to see the power of it, check out some of the Javascript demos available here: http://www.chromeexperiments.com/ and realize that these are all being computed completely in the browser! For smaller examples, see: http://code.google.com/p/flot/ http://raphaeljs.com/ and http://code.google.com/apis/chart/interactive/docs/gallery.html
That way, you don't need any fancy hosting, you just serve 'static' javascript files, and then all the interaction occurs directly in the users browser.
So it depends greatly on what you want to do.