When components like EJBs are deployed, they have JNDI names attached to them, although the names are usually very uninteresting, such as the package/class name of the EJB. When you create/deploy a datasource, similarly, you provide a JNDI name for the resource to be looked up with.
A J2EE applicaiton server maintains a Naming Service. It's required by any J2EE application server. We don't have to worry too much about it. Because people much smarter than us implement it and design the naming service, it should never fail and never go down. At least that's the J2EE promise.
How is a Java Naming service implemented? Well, it's up to the vendor. As long as it conforms to the JNDI spec, vendors can do it any way they want. In my opinion, I think the big blue JNDI server looks an awful lot like the big blue CORBA naming service, but that's purely speculation.
Wouldn't you know it, but I've got a link on my website that talks all about naming: