You have probably three options:
1. Put the addresses in the public DNS
2. Run your own nameserver, and serve the private addresses only to your own hosts
3. Put the addresses in the /etc/hosts file of each host
#1 is probably the least work, since you only have to maintain the information in one place. However, some have a philosophical objection to putting private IP addresses in the public DNS.
Here is a debate if you're interested. Note that your names would be fully qualified (e.g., db01.staging.example.org instead of db01.staging). Also note that when you change an IP address it will take some time
to propagate.
#2 centralizes the list of hosts in one place, and avoids exposing private addresses to the whole Internet. It is probably the most "correct" way, but is IMO too much work unless you're managing many names (dozens), especially if you're not used to running your own nameserver.
#3 is simple, although you need to keep the
/etc/hosts file up to date on each host. Though I don't know all the specifics of your situation, this would tend to be my first choice. One advantage is that connections between the hosts can be made without doing a DNS lookup (but only if your
nsswitch.conf puts "files" before "dns" for host lookups). When you change the /etc/hosts file on a particular (virtual) machine, it takes effect immediately.