http://en.wikipedia.org/wiki/Typeid
This seems to be a mystery to me: how does a compiler stores information about the type of an object ? Basically an empty class, once instantiated, has not a zero size in memory.
How it is stored is implementation-defined. There are many completely different ways to do it.
However, for non-polymorphic types nothing needs to be stored. For non-polymorphic types typeid returns information about the static type of the expression, i.e. its compile-time type. The type is always known at compile-time, so there's no need to associate any additional information with specific objects (just like for sizeof to work you don't really need to store the object size anywhere). "An empty object" that you mention in your question would be an object of non-polymorphic type, so there's no need to store anything in it and there's no problem with it having zero size. (Meanwhile, polymorphic objects are never really "empty" and never have "zero size in memory".)
For polymorphic types typeid does indeed return the information about the dynamic type of the expression, i.e. about its run-time type. To implement this something has to be stored inside the actual object at run-time. As I said above, different compilers implement it differently. In MSVC++, for one example, the VMT pointer stored in each polymorphic object points to a data structure that contains the so called RTTI - run-time type information about the object - in addition to the actual VMT.
The fact that you mention zero size objects in your question probably indicates that you have some misconceptions about what typeid can and cannot do. Remember, again, typeid is capable of determining the actual (i.e. dynamic) type of the object for polymorphic types only. For non-polymorphic types typeid cannot determine the actual type of the object and reverts to primitive compile-time functionality.