*MOST* modern USB modems will work in Linux because they speak CDC-ACM (you can find that driver in the kernel tree); some others need special drivers, which can be found there as well. There are also plenty of drivers for PC-Card/Cardbus/PCMCIA devices as well.
One possible caveat is some devices used to need to be "activated" with m$ before they could be used with Linux or Mac; I don't know if this is still true today.
Most all devices by Sierra Wireless (
www.sierrawireless.com), Novatel (
www.novatelwireless.com), Franklin (
www.franklinwireless.com), and Pantech appear to work especially if recent (last 5 years?).
Also, an OS-agnostic alternative is to use one of the "3G routers" out there: these have a PC-Card and/or USB input for one of these modems, and, usually, both wireless and wired ethernet interfaces for the other end. If using multiple machines in the same area, you should seriously consider this, provided you can keep your data usage down (due to the caps).
One last idea: if your company is bound and determined to keep AT&T, then go to the store and try out the sticks! You'll get subsidy-locked sticks (no T-Mobile, Rogers, etc), but you'll know they work.
Mike