I have a Mac Pro 3.1 with an ATI Radeon HD 2600 video card which I need to replace. As I don't know much about video card specs: what do I need to look out for when searching for a replacement?
The Mac Pro 3,1 is an aging computer and your video card choices are limited. Using Photoshop on it doesn't effect that use much. Of greater concern would be a good monitor with accurate color reproduction.
That said if you start looking for PCI Express x16 video cards that is a good start. You will, however, need to verify with the manufacturer if it is compatible with your O/S and system.
Unless you were getting unacceptable performance out of the old one, I would just buy a direct replacement, same for same.
Small note: the PowerMac G5 3,1 doesn't exist, and was probably confused with the Mac Pro 3,1 by the author. This is further supported by the graphics card, which wouldn't have worked with a PowerMac G5 but came stock with the Mac Pro 3,1. I submitted an edit request, but if it still says PowerMac G5, I'm not confused, just in a rush.
Graphics cards + Mac Pro = fun.
There are two kinds of graphics cards we'll be looking at here: flashed and unflashed cards.
Flashing is the process of putting a different piece of firmware on a graphics card. Why would you need to do that? Well, if you've ever looked at a Mac graphics card, they're very expensive compared to their PC counterparts. Generally, the only difference is what firmware is on there. Most PC cards can be reflashed with the Mac firmware. I'll drop this here as further reading that does a much better job explaining what I'm trying to get at.
Sound too complicated? Don't worry, you probably don't need to flash your card at all. Most modern cards (usually AMD Tahiti and newer, Nvidia is a bit weird) will work without being flashed once you get to the OS X desktop. This does mean though that certain things won't work (your screen will be black until you finish booting for example.)
If you want a Mac card that's flashed without the hassle, you can pay MacVidCards to do it for you. They charge a decent amount, but they have solid firmwares that work.
While some very power hungry cards may run into power draw issues, the Mac Pro 3,1 sports two unused mini 6-pin power ports on the motherboard for up to 150W (in addition to any supplied by the slot), which can power a card with an 8-pin connector. You will need to use converters such as these however, though they're very common and quite cheap.
Your use case
Given that you were previously using a consumer level graphics card and your monitor probably doesn't support 10 bit color, any graphics card should be fine: anything from about R7 370/GTX 760 upwards should be powerful enough, and most things slower should be fine anyways. If, however, you do want support for 10-bit color instead of 8-bit color, you'll want to look at the FirePro/Quadro series (as far as I know most consumer graphics cards don't support 10-bit color for Photoshop specifically out of the box.) These cards are significantly more pricey than their consumer counterparts, as they're marketed towards the professional market. Look for similar performance, but don't expect the same price. I'd also recommend checking out photo.stackexchange.com: they're significantly more knowledgeable than I am about the topic.
I think JMY 1000 had a good answer, but I want to add some information about power connectors.
In general, you can get away with most AMD Radeon cards (see compatibility chart here) as many of them will work out of the box as unflashed PC cards. The one thing that you lose is the boot screen (i.e. the apple logo, verbose startup text and drive selection if you're using Boot Camp). However, most of them will kick in at the login screen. On the linked chart, look for the 'OoB' column for which ones are identified by MacOS out of the box. Though they're identified and usable, that does NOT imply that you'll get boot screen, just that OSX's drivers will be able to use the card once bootup is complete.
Be careful, however, that minor differences in a card name (e.g. R9 270 versus R9 270X) does NOT guarantee that the card will work since it could have a different set of identifying values that OSX will not recognize.
The more important thing that I wanted to note was in regards to power consumption. The MacPro3,1 (and I presume 4,1 and 5,1) have two 6-pin power connectors on the motherboard which you can use for video cards that need it. Some cards have 8-pin connectors. THERE IS A DIFFERENCE, so be careful when buying an adapter to convert from 6-pin to 8-pin.
The idea is that a single 6-pin connector is spec'd to be good for supplying 75W of power. Since the Mac has two, you can provide 75+75=150W of power to a card. The PCI slot provides something around 20-30W (not entirely sure), so you won't be able to use a card that has a TDP draw of over 150-175W.
So what about the 8-pin connector? The 8-pin connector is spec'd for 150W. Some of the higher end cards draw 200W or more and thus you'll find 8-pin connectors on them. Though you can find adapters that convert 6-pin to 8-pin, you are now double exceeding the voltage that a single connector is supposed to supply and you risk all sorts of nasty "unexpected" issues that could include blowing out your power supply, motherboard, video card, etc. I will note that if there is an adapter that allows converting 2 6-pins into a single 8-pin, that should theoretically be acceptable, though I've never tried it myself.
If you're running a MacPro3,1, a relatively cheap sweet spot is a Radeon HD 6870 since they're recognized out of the box, use 2 6-pin connectors and go for about $60 on eBay as of April 2017. You could delve into the 7850 space and get a minor performance bump for about twice the money. Ultimately, you're going to be limited by the PCIe 2.0 spec of the slots which will limit the very high end cards.
The important thing is to get a GPU that is recognized out of the box so you don't have to do nasty hacks to OSX to get it to recognize the card and that secondly you are within power specs of what the Mac Pro can actually handle.