The implementation depends on your compiler. But the basic idea is that the compiler knows about types such that it can create a type_info instance for each unique type and return a reference to that instance when you use typeid.
For polymorphic types, it is quite easy to imagine (for a lack of actual knowledge). The compiler generates a static const type_info structure for each type that appears in the code. Then, if the type already has a virtual table (has at least one virtual function), then an entry is added to the virtual table which points to a virtual member function that returns a reference to the type_info structure for that class. Then, the compiler generates such a virtual overrided function for each derived class, each returning the reference to their generated type_info structure.
A similar mechanism is probably used for the dynamic_cast operator. For instance, you can have a virtual cast() function in each derived class, which tries to cast 'this' to whatever type the type_info structure of the destination type is. When dynamic_cast is done, it calls the most derived version of cast() and then works backwards by calling the base-class versions of cast() until the type_info structures of 'this' and the destination type match. If no match was found by the time you reached the most basic classes, then NULL is returned and the cast failed.
Well, you can't be sure that the above is the way it is done, since the compilers can do a lot more fancy stuff. The above was just how I implemented my RTTI system, and how many others work as well.
The point to take out of this is that C++ RTTI is usually fairly heavy-weight, because the compiler has to generate a lot of code and global data to implement it. So, use RTTI only if you really need it (for example, very often people use dynamic_cast where static_cast would do just fine, of course, not as safe, but much faster and no RTTI needed).