Any "Aircard" that works on a PC
can work on a Mac, provided the proper Mac drivers exist.
Verizon has pretty good support for Macs and OS X, although it's not that obvious on the Verizon support site. I have a Verizon Aircard for my Powerbook, and I get at least some kind of connection just about anywhere I go (and I've been all over the US). In any semi-major city, the connection is broadband.
That said, only the Powerbooks and Macbooks Pros will have a slot for an Aircard. In the case of a Macbook Pro, you'll have to wait another couple months for an Expresscard-34 Aircard to be released, and for appropriate drivers to be written.
Macbooks can be "paired" with an EVDO and Bluetooth capable phone, provided the phone has support for DUN (Dial Up Networking). This would work the same way, with the same coverage, as an Aircard.
Scott