If you're working with CMOS logic, the most common type, then power consumption doesn't depend mainly on how the circuit behaves when it sits at a steady state (input and output aren't changing), but on how it behaves when it switches from one state to another.
If you're working at the pcb level, you'll want to work out the current consumption of the circuit, and then multiply by the operating voltage (Vdd) to get the power.
The current consumption will be dominated by the output drivers of the logic. Each output is loaded by a certain capacitance. Each time an output switches from low to high, it must deliver a charge \$Q = CV_{dd}\$ to its capacitive load. Each time it switches from high to low, it must drain that charge off to ground, but we can assume there is one high-low transition happening some time after each low-high transition.
In synchronous circuits, the output transitions might happen each time the clock makes a low-to-high transition.
So the current consumption of a particular output is
$$I = f_{\rm{clk}}p_{01}Q = f_{\rm{clk}}p_{01}CV_{dd}$$
where \$f_{\rm{clk}}\$ is the system clock frequency and \$p_{01}\$ is the probability of that output making a 0 to 1 transition on any given clock cycle. You just have to add this up for all the outputs in your circuit. Then multiply by \$V_{dd}\$ to get power.
Considering a 3-to-8 decoder, you'll want to pay particular attention to the \$p_{01}\$ term. It's not just 0.25 like you might assume for some simpler types of gates.
Variations
If your gates have some static loads (like resistive pull-ups or pull-downs), you'll need to also consider their effect.
If you're working at the chip design level, you'll want to consider all the gates within the decoder instead of just the output gates, since the outputs won't necessarily have much larger loads than the internal gates.