There are two approaches: either using symmetric-key cryptography, or public-key cryptography.
Symmetric-key cryptography. When Bob receives an authentic message that has been authenticated by a key known only to Alice or Bob, Bob can deduce that the message must have come from either Alice or Bob. Therefore, if Bob wants to verify that this message came from Alice, he only needs to verify that it didn't come from himself. There are many ways to achieve this goal.
For instance, one way is that Alice and Bob can agree to prefix each message with a "direction bit": when Alice sends a message, she'll prefix it with a 0 bit, and when Bob sends a message, he'll prefix it with a 1 bit. Bob can make sure that he always prefixes with a 1 bit (he never sends anything with a 0-bit prefix). Then, when Bob receives an authentic message, he can check that it is prefixed with a 0-bit. (If it is prefixed with a 1-bit, Bob knows that he is under attack and can drop the message.) This is enough for Bob to verify that the message came from Alice, or someone Alice shared her key with -- in particular, he knows it didn't come from himself, and he knows he didn't share the key with anyone other than Alice.
Another way is to prefix each message with a random 128-bit identifier. Bob can keep track of all of the identifiers he has ever used to send a message. When Bob receives an authentic message, he can verify that the identifier on that message does not match any identifier he is previously used. This is enough for him to verify that the message must have come from Alice (or someone she shared the key with), for the same reasons.
Cryptographic protocols typically treat it as an implicit to provide this kind of protection as part of the protocol, so if you are using an existing protocol, you usually won't need to add this mechanism on your own. This is basically known as providing security against reflection attacks. A reflection attack is where a message Bob sent is "reflected" back to him, i.e., the message is intercepted and replayed back to Bob. The schemes I outlined above are standard defenses against reflection attacks. And, if the key is shared among only 2 parties, then stopping reflection attacks is enough to achieve your desired goal.
This approach is only really viable if the symmetric key is shared among 2 parties (it is not workable if the key is shared among $n>2$ parties). However, the benefit is that it doesn't require use of public-key cryptography. Therefore, it doesn't impose any significant performance overhead.
Public-key cryptography. Alternatively, you can use public-key cryptography. Assume that every party has their own public/private keypair, and every party knows the authentic public key of every other party (perhaps through a PKI, or some other means). Then this problem is easy to solve: when Alice wants to send an authenticated message to Bob, she signs and encrypts the message. In particular, she prepends Bob's name to the message, signs this using her private key, appends her signature to the message, encrypts the whole thing under Bob's public key, and sends the resulting ciphertext to Bob. Bob can decrypt, verify the signature, and confirm that this indeed came from Alice (or someone she shared her private key with).
This is just the standard sign-then-encrypt scheme for point-to-point communication with public-key cryptography. Make sure you use an IND-CCA2-secure public-key encryption scheme and a UF-CMA-secure public-key signature scheme (i.e., one that is secure against existential forgery attack).
For some intricacies about whether to sign first or encrypt first, you might enjoy this: Defective Sign & Encrypt in S/MIME, PKCS#7, MOSS, PEM, PGP, and XML.