A certificate is a package which contains an identity (a name) and a public key; and it is signed. Verifying the signature gives you some guarantee that the package is genuine, i.e. the public key is really the key owned by the entity designated by the name in the certificate. Verification is done relatively to the public key of whoever signed ("issued") the certificate, and that's a Certification Authority (CA). You may know the CA public key through another certificate, issued by an upper CA, and so on. You have to start somewhere, though, with a public key for a "top-level CA" (known as "root CA") which you know absolutely (it is embedded in the software).
That being said, SSL/TLS uses certificates for authentication, and can be mutually authenticated: both the client and the server can own a private key, and they show each other their certificates. See this answer for details.
In your case, you would have to push a private key and its certificate in the embedded device (or, better yet, have the embedded device generate its own key pair, so that the private key never leaves it); and every mobile device should also have its own private key and a certificate, where the certificate should contain the name of the mobile device (or the name of the mobile device owner). Thus, after the SSL handshake, the connection is secure, the mobile device is sure that it talks to the right embedded device, and the embedded device reliably knows which client is connected (through the name in the certificate).
Caution: authentication and authorization are not the same thing. That the embedded device knows who is currently on the other end of the line does not mean that this person shall be granted access. Generally speaking, certificates are not good for authorization, because they do not allow for fast, immediate revocation of access rights.
To produce certificates you need a PKI, i.e. some software which can organize the process of receiving "Certificate Requests" and turning that into certificates. Doing that properly requires some care, with procedures to follow. Some software can guide you; I usually recommend EJBCA, which is free and opensource.