In the users Preferences -> Mail -> Accounts make sure that the Signature you created is selected in the Signature drop down at the bottom of the Primary Account Settings.
(The exact path in the preferences is a bit different in 5.0.x, but that should point you in the right direction)
You might also want to take a look at this bug:
Bug 4720 - add system/domain wide mandatory signature
It is supposed to be coming in 6.0.3.