There are a lot of ways to do robot odometry, each with their advantages and disadvantages. There is no one best solution; it all depends on what you need the system to do and - as my father who worked on ultra-high precision guidance systems would remind me - how much you're willing to pay.
Wheel encoders on driven wheels
This is the tried and true method: measure how much each wheel turns, and use this information to figure out the robot's position. You probably already have the hardware, and the software is pretty straightforward. But, as you've already ascertained, when the wheels slip, what you measure is actually how far the wheel spins, and not how far the robot moves. If you assume that the wheels never slip, you can derive your position from only two encoders.
Wheel encoders on non-driven wheels
This is an attempt to deal with the wheel slip problem caused by the above method, and could use encoders on omniwheels or a device similar to a traditional ball mouse. The problem is that this tends to result in fragile and/or high-precision components riding along on the carpet, risking damage, causing a small amount of friction, and picking up dust. Like the above method, you only need two encoders if your measurement wheels are parallel and you assume they don't slip. Three encoders is better; a trackball provides two axes but needs at least a third axis so you can determine rotation.
Pure IMU
Use a gyro and dual-axis accelerometer to calculate position. You could also use an off-the-shelf IMU, which typically includes a 3-axis gyro, a 3-axis accelerometer, and maybe a 3-axis magnetometer. The advantage is that an IMU is completely independent of your robot kinematics - it doesn't matter what drivetrain configuration you use, the algorithm is exactly the same. It works even if you're pushed sideways.
Mathematically, it's pretty straightforward to implement, but as Ether and others have pointed out, IMUs suffer from accumulated error. A gyro isn't too bad, since you only have to integrate rate to get the heading. But with an accelerometer, you're integrating twice to get from acceleration to position, and a tiny error can accumulate and hurt you pretty quickly. And with a 2-axis sensor, if your robot tips so that the accelerometer is no longer horizontal you'll be hosed in no time.
This is where my dad chimes in and says that if you're willing to pay $1M, you could use an IMU to get sub-millimeter accuracy for days... but in FIRST we have a parts budget to worry about.
Hybrid IMU/Encoders
It's pretty common to use wheel encoders to track distance and a gyro to measure heading. For our 15-second autonomous mode, you don't have to worry much about collisions and wheel slip, so the encoders are a pretty good solution. This is simpler and more accurate than what you'll probably be able to do with an inexpensive accelerometer.
Mouse sensors
Mouse sensors have a lot of advantages: they don't have to contact the tracking surface, have very high resolution, and are dirt cheap. However, they have several drawbacks:
they are very sensitive to height, they have limited tracking speed, and they typically have to be very close to the tracking surface. The focus, tracking speed, and sensor height problems can be solved (or at least mitigated) by using a lens to focus the sensor on a larger patch of surface. The scale part of height sensitivity
has also been solved, but it's a little trickier to implement.
Laser mice and optical mice work on exactly the same principles, and are subject to the same errors. Even if we could use laser mice, they would have the same problems.
A major part of my senior design project included making a robot navigation using a set of 6 optical mice, and I've posted some of my work on my website:
http://www.botsnlinux.net/school_projects.php. In the unlikely event that I actually have free time this summer, I would like to adapt my system for an FRC bot and see how well it works. My gut sense is that I can probably get it to work at least as well as an encoder/gyro solution, but it will require a lot of experimentation and tuning. Unless there's a compelling advantage (such as in Lunacy), it probably isn't worth the effort during the build season.