First of all, find out if you're an Alltel customer that's been converted to Verizon. If your bill says Verizon Wireless, you've been converted. There are some Alltel customers that haven't been converted. Some are going to be converted to AT&T, some are going to remain individual little regional pockets of Alltel (don't ask me how or why, that's what I was told during what little Alltel training I received).
If you are a converted Alltel customer, it's easy. You most likely are eligible for a new phone, whether by time elapsed in your contract or due to promotions (trust me on this one, VZW is doing their best to get legacy Alltel hardware out of the system so they won't have to support it). Just upgrade your phone, the new contract is a VZW contract, and it will just go into effect overriding (in essence) the Alltel contract. You won't have to pay an ETF, or port your number. If you're a converted Alltel customer with legacy hardware, and you're not eligible, call into customer service (*611, option 4, then say customer service) and you can most likely get some sort of help in getting the phone.
If you are not a converted Alltel customer, then you're going to have to do it the hard way, port your number to VZW when you purchase the phone, and the port process will automatically disconnect your service with Alltel. You will need all of your Alltel account information with you when you port/purchase. By the way, this also applies to anyone else porting from another carrier to VZW to get the Incredible.