I assume you're looking at a Voodoo5.
If that's the case, the fans are connected for power to the card itself, so there's no need to worry about where the fans plug into. You do have to plug four pin power connector from your power supply to the card, though, but if you buy the card retail there will be a Y adapter for this in case you're out of power connectors.
As far as replacing the fan on your TBird, if you intend to overclock it, yes, by all means get a top of the line fan. TBirds run VERY hot, even at default speeds, so good CPU and case cooling is a must.
The best pre-made fan out there for your processor would be the Alpha PAL6035 w/Delta Fan, which can be had at
http://2cooltek.safeshopper.com for around 30 bucks.
If your case has pre-cut holes for intake and/or outtake fans, I'd go ahead and add those as well. The CPU fan can only get the processor so cool if the ambient temperature in the case is high, so case cooling helps quite a bit.
Xayd