I just bought an 04 from a dealership in Texas. (D/F-W area), and I live in Seattle. The truck is clean, well, no rust, it WAS dusty, those folks down there need to learn to detail a vehicle! anyway, Im VERY happy so far, the truck was as advertised, and 8 grand less than other stuff I found here. Im not sure what trucks cost where you are, but my plane ticket, motel and gas came to under 700 bucks, and thats worth a trip to DFW!
I found mine on Autotrader.com, put in my serach criteria, and poof! I just didnt put a limit on distance. I would keep in mind that a GM dealership has a reputation to take care of, so I would be more comfortable with them than a private party, and certainly a used car lot. But, that's just my personal experience, and $.02.
the folks there were super polite, and the sales guy even picked me up at the airport at 6 am!!!
I would suggest getting the VIN #s on whatever trucks you are interested in, and make a friend in a local dealership, have him run the Vin for you, and they can tell you if any warranty work was done. I dont trust Carfax to have ALL the facts, and most dealers will send you a carfax on the cars they sell. If you want to know more of how I did it, send me a PM.