If you're looking for a commercial solution, check out NorthStar from Evolution robotics.
It uses an IR transmitter on the ceiling or wall and a receiver on the robot to localize fairly well. (1-4cm according to their specs) They also have vSlam as part of their ERSP package, which works using an inexpensive web cam, but the ERSP software is pretty expensive unless you're an educational user.
I've also looked at Carmen, a free software toolkit from CMU.
It sounds like that will do localization reasonably well, but right now I believe it depends on a laser range finder to work properly. It looks like player/stage
implements a basic Monte-Carlo based localization scheme in their amcl driver which could be used with sonar data, but you'd probably not get great results without some additional work there because of the noise and error rate in typical sonar systems.
Odometry works pretty well by it's self as long as you're on a flat, smooth surface, until you have to turn. :)
Last I heard was magnetic tape stuck to the floor in such a way that it would not wear due to being stepped on or rolled on. This allowed the robots to measure to within fractions of an inch exactly where they were at any given time, and could divert into rooms or racks, then rejoin the mag tape... But this was years ago at the IBM facility in Boulder, Colorado.
This is still a pretty common approach. The big warehouse robots at the coca-cola bottling facility hereabouts use this same strategy, w/ permanent magnets (not tape) embedded in the warehouse floor itself at regular intervals. Not very interesting computationlly, but highly reliable -- which is important with machines this large, capable of doing a great deal of damage to people and property if they run astray.
The latest and greatest in warehouse automation can be seen at Ralph's in the Los Angeles distribution center. Everything comes in by truck... rail is non responsive, non competitive and with an attitude. Trucks are unloaded and the pallets put into bins with a bill of material for all items. Then, across the street, is another warehouse where pallets are transported as required and put into slots, again bar code date on all items. But the clever thing here, is that they use humans to rush from box to box to fill each store's order and actually do it according to the shelf height level of the store. For example, Banana Crunch cereal is always at the top of the shelf, so when a carton of this stuff is taken from the major carton, it is loaded on the top shelf of the loading cart. When the individual store receive their restocking order, the stockers need only reach across with their loads. And so it goes. These individual humans scoot about the warehouse as though on roller blades and even faster. They are compensated by the number of orders filled during their shift. And no robotic system has yet come close to beating them except for the interface robotic ASCARA (automated Storage and Retrieval system) which deals with pallet sized BOMs and not details.