How do I find where an environmental variable got set? I installed a program to try it out, and decided I didn't like it so I moved the app to the trash.

Today, in my shell, I noticed that there are a couple of PROGRAMNAME_BLAHBLAH environmental variables set.  I'd like to remove those, too.

I don't even have a .bashrc or .bash_login, so I grepped every file I could think of (~/.* ~/Library/* /Library/* /etc/*).  The only place these variables turned up was a file ~/.MacOSX/environment.plist, so I removed it from there (Xcode can edit binary plists), but new shells still have these variables set.

What other files does Mac OS X 10.7's terminal/bash run on startup?  How might these variables get set?

Or is it something funny like "need to reboot after editing environment.plist"?
~/.MacOSX/environment.plist is read at session start. If you want your change to it to be tested immediatly you have to restart your session.
A restart of the system is useless.
You can edit this environment initialisation file with:

plutil -convert xml1 environment.plist
vi environment.plist


I advise you to simply recover it to its version prior to your software
installation.

Other hint, check all the files which were modified on the date
of installation of your unwanted software.
If you installed your software 15 days ago, you can perform this with:

find / -mtime -16 -mtime +14 -ls