What is the best way to estimate the power consumption of an Atmega328p microcontroller?

Because these microcontrollers can operate at 8Mhz and 16Mhz, is the power consumption a linear function of frequency? i.e. does operating at 8Mhz consume 0.2mA * 8 = 1.6 mA of current?

First of all, the 328 can run at many more speeds; its maximum clock speed is 20MHz, and at least down to 32kHz is supported, possibly lower. Anything in between is also valid.

As for the power consumption, have a look at the datasheet, in particular the graph in section 33.1.1 (ATmega328 Typical Characteristics -> Active Supply Current):

As you can see, the current increases roughly linearly with clock speed. In my experience, there is a "static" component to the power consumption that is added to the speed-relative power consumption, and this part may dominate at very low clock speeds. But this will depend on supply voltage and enabled peripherals.

What is the relationship between voltage and the power consumption? I understand that DC power is defined by W = VI, however, if I were to operate at 3.3V, wouldn't I pull less current? I'm not sure if that is a correct assumption however.

Transistor-based ICs generally draw less current at lower voltages; you could approximate them as a resistive load (which is not quite accurate but fair enough for an estimate). Again, the datasheet has a helpful graph (same section):

As you can see, the relationship is even stronger than linear, it has a slight quadratic curve to it. At 5V it draws about 1mA, for 5mW power. At half that, 2.5V, it's only 0.4mA, resulting in 1mW power. Low voltage is a must if low power is your goal!

I assume that the listed power output also excludes any additional power that the chip is sourcing to I/O (i.e. supplying 10mA to an LED would increase the total amount of current going into the micro controller).

Correct.

However, do certain operations within the microcontroller cause it to consume more power? I'm specifically interested in the case of implementing serial communications like SPI.

Yes. AVRs, including the 328, can disable many of their internal peripherals, such as SPI, UART, ADC, timers, etc. Disabling them will lower your power consumption. The question is by how much; in my experience those peripherals draw negligible power compared to the main CPU at 5V/20MHz, but at lower clock speeds or when the CPU sleeps a lot, the peripheral power can be significant. For low power, disable anything you don't need.

A note about datasheets: they tend to present best-case scenarios. I suspect the power consumption figures and graphs in the datasheet are with all peripherals disabled.

The information in the datasheet is helpful, but if you want to get the most out of your power, you need to do experiments and measurements. Measure the current draw:

• At different clock speeds
• At different VCCs (observe the minimum VCC for a given clock speed!)
• With each of the peripherals disabled or enabled
• In the various sleep modes
• Using the various clock sources

In general, to optimize your 328 project for power, take these steps:

• Optimize your code. The fewer cycles you need to do your work, the less power you need.
• Run the 328 at the lowest clock speed you can.
• Run the 328 at the lowest voltage you can (considering clock speed).
• Let the 328 sleep when it has nothing to do.
• Disable all peripherals you don't need.
• Aim for using the internal 128kHz RC oscillator if at all possible.

It really depends on how much work your 328 has to do. At 20MHz/5V, an active 328 draws about 20mA = 100mW, but at low clock speed and voltage, 1mW is very doable. Big difference.

When operating at low voltages, close to the tolerance of the 328, you might also want to consider how to deal with battery voltage drop. Discussing battery capacity and voltage drop is beyond this answer, but this EEVblog video is an excellent starting point.

I've found that measuring equipment for such high-resolution measurements is too expensive for my development budget and prohibitively advanced for my skills to DIY.

Instead I've found that charging a large capacitor and powering the circuit with that and seeing how long before it browns-out, is a good way to measure relative differences in hardware setups.

If your software is organized in such a way that it mostly does the same things given the same inputs, you can easily test and see how much power consumption is affected by changing certain hardware settings.

You can vary the charge voltage and the capacitance to get a measurement domain within acceptable bounds. Sometimes it's too long to wait to see if it will take 30 seconds or 25 at a certain setting, if 0.3 vs 0.25 could have been sufficient. Horses for courses and all that.

It is not too hard to estimate the energy held in a capacitor charged to a certain voltage, so total energy consumption can be estimated/calculated as well.