Just to amplify some of the rather important points made in comments ...
Use an ATtiny24 not an ATmega328
The project you want to copy uses an ATtiny24 for good reasons.
[The] ATtiny24A microcontroller ... included all of the things the team were looking for – it was working with voltages as low as 1.8V, consumed small amounts of current and had enough i/o pins.
ATtiny24 vs ATMega328
- lower cost
- smaller package (DIP-14 vs DIP-28)
It has plenty of GPIO pins (~12) compared to a DIP-8 ATtiny45 for example (5-6).
If you are making a large constellation of interacting autonomous objects, you can get more for your money by using parts that are no bigger/expensive than they need be.
If money, size and power-consumption are no object, you might use a 144-pin AT32UC3C064C for maximum future flexibility. Personally I think half the fun of this sort of project is squeezing it into a small device.
Loading software
You can use an Arduino Uno to program (load software onto) an ATtiny24 on a breadboard.
To do this you first load an "ArduinoISP" program ("sketch") into your Arduino Uno. You can then use this to load programs onto an ATtiny24 or any AVR microcontrollers that allow loading software via an ISP interface (I think there may be one or two that don't).
If your Arduino IDE isn't set up for the ATtiny24 (see below) there are other free tools to compile programs and free programs to load those programs onto an ATtiny24 - for example avrdude
Compiling software for an ATtiny24
You can use the Arduino IDE to write and compile programs to run on an ATtiny24. To do so you add a suitable "core" to your Arduino IDE's "hardware" subdirectory (folder). You can obtain a suitable "core" from code.google.
Note that many online tutorials mention the "core" from High-Low-Tech at MIT but that "core" doesn't include the ATtiny24 so try the code.google "core" instead.
Using coin-cell batteries
See other answers - You should choose a microcontroller no more powerful than the minimum needed to do the job. Set the clock speed low. Shut down unused features and make maximum use of low-current sleep states. AVR has documentation that specifically covers low-power applications.