Here's what I did to get Python running on my HTC Incredible:
Step 1: Install a barcode scanner, so that it's easier to install custom apps: Install ZXing app
Step 2: Install the SL4A application (Scripting Layer for Android) by going to the SL4A project home page and running the previously installed "Barcode Scanner" app (the title on the icon of the ZXing app) to scan the SL4A's barcode (or just click the link if you're reading this on your Android). This downloads a .apk file which you then run to install this app directly onto your phone, since it's not yet available in the Market. You might have to change your phone's settings to allow installing non-Market apps -- go to Settings / Applications and make sure "Unknown sources" is checked.
Step 3: Install the Python interpreter:
- Run app SL4A.
- Press the menu button, then View, then Interpreters. You should only have Shell at first.
- Press the menu button, then Add, then select Python 2.6.2. After the .apk file for Python downloads, run it to install it.
Now you can edit and run Python scripts on your Android, and you have a lot of the Android functionality available. Here's my first test script:
droid = android.Android()
You can press Help to see the API that's available, it's a subset of the entire Android API.