I think the problem is that without signing-up, there's no indication that it's a paid service, let alone what the price actually is.

A "Pricing" page in your navigation would be ideal, IMO. Even an entry in the FAQ ("How much does this cost?") would suffice, especially if it's the top item.