You must connect them (Edit: You must connect ALL INPUTS) to something, otherwise they will float and pick up noise. This can cause increased current consumption (because the MOSFETs inside the gate operate in their "linear region" where both can conduct simultaneously, causing a current path across the supply rails) and sometimes other misbehaviour.
You can connect unused inputs to VDD, VSS, or any other signal point in the circuit that will be at a clearly defined logic level, such as the output of any other gate.
You know about decoupling capacitors? Each IC should have a small-value capacitor, typically 0.1 µF, ceramic, connected between its VDD and VSS pins as closely and directly as possible. This is needed because when CMOS gates switch, there is a brief time when the MOSFETs inside the gate conduct simultaneously, as I mentioned above. This causes a "shoot-though" current burst, which can pull the supply voltage down briefly and cause other gates or other parts of the circuit to misbehave. Each decoupling capacitor acts as a local reservoir that supplies the little bursts of current and keeps the supply rails from dipping.