It varies greatly from an hour or so to as long as 3-4 days. I've found com/net will take longer initially than info/biz since Verisign only updates the registry twice a day. Supposedly, they are working on increasing that. .Info seems to update within a few minutes.
the time it takes to resolve will also vary with different end users. Partly due to the settings in each company or ISP router as to how often they update their database and how busy they may be. I've seen a difference in propagation between home and office computer of as much as a full day using different ISPs.
BTW, I have a hosting account with a number of domains parked. If I need to publish quickly before propagation, I can set up the parked domain that is already using the same DNS servers to resolve and can access the new host account instantly using the parked domain, and reparking it on the new host account. This allows me to publish to the host before the new name actually resolves, even using shared IP's. When complete, I can move the parked domain back to its normal account and access the website via the new domain.