Answer replaced (and turned Community Wiki) due to numerous updates and notes from various others in this thread:
- ICOs and PNGs both allow full alpha channel based transparency
- ICO allows for backwards compatibility to older browsers (e.g. IE6)
- PNG probably has broader tooling support for transparency, but you can find tools to create alpha-channel ICOs as well, such as the Dynamic Drive tool and Photoshop plugin mentioned by @mercator.
Feel free to consult the other answers here for more details.