In order to get the declare war dialog you must find a barbarian unit that is not within barbarian territory, and then move into its tile by right-clicking on the barbarian unit (or right-click-and-hold on any tile, drag the targeting circle onto the barbarian unit's tile, and then release the right button). If you attempt to move into the barbarian unit's tile by clicking the goto icon (or pressing the shortcut key for that action, <G>) then the dialog will not appear. Also, if the barbarian unit is in barbarian territory then the dialog will not appear.
Alternatively, if you attack any HN barbarian unit (which will typically only be animals) then you will receive a declare war dialog regardless of where the barbarian unit is located.
After the early stages of the game there may not be any animals left and it may be difficult to find other barbarian units outside of barbarian territory. In this situation it is possible to use spells to declare war on the barbarians. For example, if you cast Scorch while in barbarian territory you will declare war on the barbarians. Likewise, if you strike a barbarian unit with an AoE damage spell (such as Maelstrom) then you will declare war.