Strictly speaking, the use of the term "signature" about HMAC is improper; it is widespread, but still incorrect: signatures are about asymmetric algorithms with a public and a private key, such as RSA.
HMAC uses a secret key (i.e. a bunch of arbitrary bytes) which is used for computing the MAC and for verifying it (it is actually verified by recomputing it). So, in your problem, yes, the server must store either the secret key, or some data which is enough to recover it.
Note that the secret key K can be derived from the password in a non-invertible way. E.g. through a hash function or, better yet, with a Key Derivation Function. The server will store the key K "in plaintext" and knowing key K is enough to produce valid HMAC values. However, this forces an attacker to use some specific software for that, not the standard client which requests a user password. Depending on the context and your attack model, this may or may not be a security improvement.
A way to achieve what you are looking for, but with higher complexity then a plain HMAC, is to use SRP. SRP is an asymmetric key exchange protocol with mutual password-based authentication, with the following characteristics:
- No need for public key distribution (PKI, certificates...).
- Client authenticates server and server authenticates client, in the same pass, even in the presence of active attackers ("Man-In-The-Middle" attackers are defeated).
- No active or passive attackers learns enough information to perform offline dictionary attacks (a dictionary attack is guessing the password by trying random words; the attack is offline if it can be done without interacting with the honest client or server for each guess).
- What the server stores is not enough to learn the password or impersonate the client (but it allows offline dictionary attacks, which is unavoidable).
The key which results from the SRP protocol can then be used for a MAC algorithm such as HMAC. It needs not be stored: it is just kept in RAM for the duration of the session.
SRP can be integrated in TLS, as explained in RFC 5054. The easiest, most standard supported way to use SRP in your context would be to use HTTPS (i.e. HTTP within a SSL/TLS tunnel) with the TLS part using SRP for key exchange. GnuTLS is an opensource implementation of SSL/TLS which supports SRP.