How soon does the ammonia start turning into nitrites?  I've been cycling my tank for a while (fishless) and have seen no change.

Hello!
It should just take about two weeks at most for ammonia to show, and after that another two weeks for the first nitrosomas to establish. Have you tested both ammonia and nitrites lately? If so, what are the readings?

Ammonia won't appear on it's own, you'll have to add fish food to the empty tank, which will decompose and let out ammonia. Which will encourage the beneficial bacteria to start multiplying to deal with the problem
There are other methods of adding ammonia as well! For example, you could bury a small shrimp or piece of fish meat partly in the sand and leave it there for a few days until you notice the ammonia going down. There are people who add pure ammonia, drop by drop to their tanks, but if you choose this method, you need to be really careful, and test the water daily!

If you want to speed the cycling process more, you could buy a bottle of bio filter media. That's pretty much beneficial bacteria in a bottle, and even if it won't make the tank cycle instantly it will still be of big help in the process. You could even keep a few small fish there while using it to keep the ammonia production in the tank rather natural.