Apologies if I cover anything you already know below. :-)
Do I have a dedicated, private server, or not? How can [I] tell definitively?
(Re-) Ask your hosting provider. Specifically, ask them if there is a dedicated hardware-based server that you alone exclusively control and do not share in any way with anyone else. If they say no, then you are not using a (truly) dedicated server.
"Private Server" could mean anything but often this is a term used in lieu of "Virtual Private Server" (VPS).
These differ from "shared" hosting in the sense that shared hosting simply jams all the resources and process onto a single hardware device with one OS and likely little resource management. Virtual Private Servers use virtual machines to emulate dedicated hardware - so each "fake" server occupies the same physical server (and it's resources) but acts like it is a totally separate device (complete with its own OS, memory limits, etc.)
VPS hosting can be better than shared in the sense that resources are potentially better allocated than with shared hosting and physical servers that are used for virtual hosts tend to be more powerful simply because hosting multiple virtual machines is resource intensive. That said, it still is generally not the same as having a truly dedicated server.
Regarding whether you have a VPS or shared hosting -- again, ask your hosting provider. Assuming they are honest, they should be able to tell you exactly how things are managed.
I was told that I should code the database host as server76.XXX.net - which sounds like a sub-domain to me[.]
Regarding the sub-domain, these are simply resource pointers.
The resource itself could be a folder on a system, a web application, a single machine or a group of machines. Sub-domains in no way indicate that a resource is a "shared" host in the sense we are discussing here.
Sub-domains are mapped to resources via a combination of hardware (e.g. routers, etc.) and software (e.g. Apache web server, etc.)... which why a sub-domain can point to both a single machine (e.g. somename.dynamic-home-dns.net) or multiple machines (mail.yahoo.com, translate.google.com - 'cause we all know those services run off exactly one shared server... :-D )
That said, if it is a single machine, it still says nothing about how that machine operates or whether it is physical or virtual. Likewise, it could be running all kinds of processes, it could be a dedicated database machine you share with others or it could be totally dedicated to the task of processing your database alone.
They won't even let me telnet in ("in case you mess things up"), just create databases[.]
This isn't totally out of the ordinary and unfortunately doesn't give any clues about the situation either, since not all hosting providers give Telnet/SSH access to machines regardless of being dedicated servers, VPS machines or shared hosting.
That said, as comments from the peanut gallery, this isn't an unreasonable thing to expect from VPS or dedicated hosting and I would be sorely tempted to look at other providers which would allow this.