Can I easily redownload all my apps if I get a new phone? I am considering buying a new phone. Is there a way to easily redownload all of my apps onto the new phone without having to search for each one individually?
Yes you can.  There are a number of utilities around to do backup and restore, as well as other options.

I recently moved from the HTC Magic to the Desire HD.  The way I did it was to use a free AppBrain account.  This has a few advantages, in my opinion:


You can search for, read about and
tag for installation, applications,
on your computer, with a larger
screen/keyboard etc. 
You can organise
apps into groups if you have multiple
android devices. 
You can share your
apps with other people.


You can check out appbrain at http://www.appbrain.com/
If you just want straight backup and restore, Titanium backup, as mentioned by others, is a good choice. ( http://www.matrixrewriter.com/android/ )

You can also find both of them in the Android Market.