Level 1If you look at the python documentation, they cover some of the historical methods of web programming . 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 2Now, 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  and , 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.
So it depends greatly on what you want to do.