Long wait to get Hotspot feature going on Verizon iPhone 4S
Just did this the other day and it took less than 30 mins, its probably ready instantly after you add it to you account, but in practice it takes longer because it did not just start working automatically on  the phone, the phone needed to call Verizon to get updates to what it could do first. I only needed to call them so that they could tell me to do steps 1 and 2 below. Knowing that you don't even really need to call them.

The next thing you do after adding the Mobile broadband features to your account is:


Reboot the iPhone
Dial *228 and then select option 2 (the one for updating phone's mobile or roaming features)
Then you are good to go and set up the hotspot via USB, Wifi or Bluetooth.


Note: if that fails then they say:


  ... please call us from a different device at (800) 922-0204