The question is VERY dependent on several factors,
- The Exact model/type of card you are planning on using
- How you are planning on using the card (i.e. just to drive the display, or more intensive 3d-accelerated stuff)
- The features you need.
In general, almost any card you can use will be supported with some driver to drive the 2d display (i.e. you should be able to boot and run gnome/unity). The open source vesa driver will support the majority of cards made since the early 90's in a relatively low resolution graphics mode.
Where it gets very muddy is the current state of affairs for more advanced drivers that will allow you to exploit the hardware acceleration offered by graphics cards.
In General, nvidia has better driver support for the linux community. The closed-source nvidia driver (available as a binary blob in most linux distributions) supports cards going back to approximately 2004 (the Geforce 6xxx series being the earliest supported card). Since this is a current driver, and supported by nvidia it provides good support of all major card features and is compatible with most modern linux distrubtions. Where you could get into trouble is with older cards (say a Geforce 4), where you would be forced to use a legacy version of the nvidia driver, modifications to the kernel since then may have made the driver incompatible with modern kernels and potentially Xorg and may require a legacy linux system to use the legacy proprietary driver. However, if you are using such an old card, fully supported hardware 3d acceleration may not be necessary and you would be content with a generic 2d driver.
ATI also provides their own driver for linux systems, which will support their range of cards with full features. HOWEVER, the cards that they support at any given time is much smaller than nvidia. Whereas the current nvidia driver support consumer cards back to the 6000 series, the ati driver supports cards back to the 2xxx series (about 3 years back). For other cards ATI support is a salad of overlapping legacy proprietary drivers, open source drivers, and generic drivers. Keep in mind that installing a legacy proprietary driver (for which support is dropped) is a HUGE pain in the ass, as the driver has not kept up with any updates to xorg or the kernel interface and most likely will not work unless you use a legacy linux system.
ON THE OTHER HAND, because ATI provided open source support for some time in the past, open source support of ati cards is much much better than nvidia, especially when it comes to legacy cards. Unless you are using the latest and greatest ATI card that is supported by their linux driver, the open source driver is probably the better option to hacking a legacy proprietary driver on your system. Because of the previous official support, the open source radeon driver supports a large selection of oldish cards with most hardware features.
If you are looking at brand new cards, both ATI and Nvidia provide proprietary drivers that will power your cards. Historically, Nvidia has kept up linux support for their older cards much longer, with ATI you might be out of support 2 years down the line. If you just want to display your desktop, almost any card made by either manufacturer within the last decade should work just fine.
ATI: Shady proprietary support when it comes to cards supported, Well developed Open source support
Nvidia: Decent proprietary driver, almost non-existent open source support.
LOOK UP THE CARD YOU ARE LOOKING TO BUY IN GOOGLE, with a query like
Radeon XXXX ubuntu 11.04 (The only reason I say ubuntu is because they tend to have more howto hits than other distros, if its doable in ubuntu its doable on most other distros too) and see if people have had success using it. Unfortunately, the reality of the situation is that manufacturer linux support is unpredictable and open source support is very difficult to bring up to speed due to the sheer volume of cards and changes that manufacturers introduce every year.