when i had mine shipped it was a hassle, but what we ended up doing was (and this was kosher with UPS/Fed Ex) wrapping them up in protective plastic, not saran wrap, the heavier stuff that they use to wrap furniture and stuff in. basically you put whatever padding that you want on the wheel, wrap it a lot with the plastic and place your shipping label on it. its a good idea to wrap around once more over the label for safety sake. do this with each wheel so you have four packages, it would be too bulky with all four or even two in one package. a word to the wise, put some sort of moisture absorbing/eliminating substance in with the wheel as there will almost ALWAYS be stray moisture in the air or on the wheel. would hate for that to ruin a chrome finish or something. it can be a PITA, but it can be done.
We (FedEx) handle alot of tire/wheel combos fot the Tire Rack. What they do , and it seems to work well, is to cut cardboard larger than the wheels an the plastic band the cardboard to the wheel tire combo. You can double up the cardboard or get some really heavy duty stuff.