What's making the clicking
Although there might be other things going on, due to the symptoms, its probably the starter solenoid. When your key turns in the ignition, it completes a relatively light circuit between the battery and the solenoid. The solenoid in turn snaps two contacts together (click) completing a much larger circuit between the battery and the actual starter. The reason they have these is so the large current doesn't have to flow through the key (or the ignition - you get the point)
Repetitive clicking
If you're experiencing repetitive clicking upon turning the key in the ignition, the most common problem will be a dead battery, or bad connections between the battery and the car. The battery still has enough juice to close the solenoid's contacts, but the additional drain from the starter will reduce the current to the point that the solenoid can no longer stay closed. When the solenoid's contacts separate though, the larger circuit opens, reducing the drain on the battery, which allows the solenoid to close again, repeating the process. (Hence the repeated clicking.) Since you said you just replaced the battery, I would check all the connectors. Repeated clicking indicates that the solenoid is fine. It is supplying power to the starter, but the battery or cables are not able to supply the current to keep it energized. If you're hearing repeated clicking, it has to be a fault prior to the solenoid.
Check
- Your battery charge
- Your battery connections/cables
- Ground cables
Single Click
If you're hearing a single click, it is likely either your starter or your starter solenoid. Your solenoid contacts might be burnt, not allowing enough current to go to the starter, or your starter motor could have a dead spot.
Often times this will be in the engine bay (under the hood/bonnet), but sometimes it will be connected directly to the starter, which is often slightly harder to get to. However, I'd start with the solenoid, as that's cheaper and usually easier to replace than the starter.
If it's not the solenoid, it's probably the starter. For now, you can usually just rock the car back and forth to get the starter moved to a different position, then the car should start. If this is the first time this has happened (although you might not know, seeing that you've had the car for about a month), it'll probably be a couple years before you even see this problem again. However, it'll only get worse, so when you have spare time (and a little spare cash for the starter), you can go ahead and replace it. You can usually find a video on YouTube, or you could ask a question here as well. For most cars this won't be too hard of a surgery.