How to do basic authentication?

I think anything that your client can decrypt, someone could figure out how it works and decrypt it with a fake client. So unless you're trying to authenticate users instead of the client app, I don't think it's worth doing.

I want to authenticate that a client is using my app (and not just sending correctly formatted data to my server).

You can't really do this. There is no way to know if it's your program which is contacting the server (assuming the protocol is followed).

Currently my server will get a message from a client, read it, then send a response back. With this setup, my game could easily be spoofed. Someone could easily see what packets get sent/received to create a client that does exactly what my game does and talk to my server. Is it worth it to try to prevent this?

Could I have some sort of key embedded within the game used to decrypt a challenge value my server sends to the client? If I were to try to do some basic authentication like this, what libraries are available? I have looked at Google KeyCzar, but I'm not sure how to use it for my purposes.

IMHO - The only way to go is to implement and check the game rules on the server. For each client action you receive, have a list of pre-conditions the server will check in order to allow it.

If you do this it doesn't really matter whether the player is using your client, or has written their own, or even is playing the game using telnet and very fast typing ;)

Authentication has it's uses, but usually only to verify the actual identity of the player (not their client).

[Edit] I only answered half your question. You can encrypt the packets if you like, but think about whether it's worth the trouble. Does it matter if someone re-implements your network protocol, as long as everyone plays by the rules? This is where server validation comes in.

And regarding libraries, it depends on your programming language. For C++ you could look up OpenSSL, PolarSSL, YaSSL, and many others.

Thanks for the help guys. That was my original inclination - to just let anyone communication with the server. So is this generally the standard for cheap online games that don't require a user ID? I'm just hoping nobody tries to take advantage of this.

It seems to be the standard for all games. If you could write a Call of Duty client or a World of Warcraft client, the server wouldn't know the difference. But if everything you do in-game is checked by the server you don't gain anything (in the cheating sense), which means for the vast majority of people it's just a waste of time to do such a thing.

Packet encryption can be a defense against session hijacking and spoofing by third-parties, but it doesn't protect against the player themself. If their client has the encryption keys then so do they, so they can send what they like. It's up to the server to decide if their messages are reasonable.