Any PA needs speakers, something to power the speakers, and something to feed the amp a line-level signal. If you were ONLY going to feed your PA a single mic you could use a mic pre-amp, but usually a mixer is pretty much a requirement.
First, set your budget (in your case $500). Then the questions to ask are -
1) How many mixer channels do I need (i.e. how many mics and instrument sources) and/or can I afford?
2) How LOUD do I need to be?
then (once you have answered the first two)
3) Do I get a combo mixer/amp, or seperate units? Or do I get an entire packaged system with speakers?
4) If buying speakers seperate, what will work well with the mixer/amp I picked out?
Now I agree you will be hard-pressed to find anything new in a store for $500. Used stuff might be the way to go. Since you are starting out on a tight budget, and it sounds like you guys have decent guitar and base amps already, you might want to concentrate on finding a PA for vocals only. A lot of bands do this starting out. Also you will probably want to look at a combo mixer/amp. As JDavis & Cave Dweller said, a seperate mixer and amp is more flexable, but you will get more bang per buck with a combo. Peavy makes some decent cheap combo units. Check Guitar Center, somtimes they have sales on beginner PA packages that include mixer/amp and speakers.
Also remember that if you do well and start getting large bar gigs a lot of bars have their own PA equipment, or you can rent it per gig. Right now look for something for doing house parties or street corners and such.
Good luck...