RESTful Web service or API for a Python program in WebFaction
Well, your question is a little bit generic, but here are a few pointers/tips:

Webfaction allows you to install pretty much anything you want (you need to compile it / or ask the admins to install some CentOS package for you).
They provide some default Apache server with mod_wsgi, so you can run web2py, Django or any other wsgi frameworks.
Most popular Python web frameworks have available installers in Webfaction (web2py, django...), so I would recommend you to go with one of them.
I would also install supervisord to keep your service running after some reboot/crash/problem.

I would be glad to help you if you have any specific question...
I have developed a few python programs that I want to make available online. 
I am new to web services, and I am not sure what I need to do in order to create a service where somebody makes a request to an URL (for example), and the URL triggers a Python program that displays something in the user's browser, or a set of inputs are given to the program via browser, and then python does whatver it is supposed to do.
I was playing with the google app engine, which runs fine with the tutorial, and was planning to use it becuase it looks easy, but the problem with GAE is that it does not work well (or does not work at all) with some libraries that I plan to use.
I guess what I am trying to do is some sort of API using my WebFaction account.
Can anybody point me in the right directions? What choices do I have in WebFaction? What are the easiest tools available?
Thank you very much for your help in advance.
Cheers