Login as admin. Follow the link 'Languages' in the 'Administration' box. Then select language to edit, i.e. English, etc. In the 'Select topic' box select 'Labels'. In the field next to it type Other and press button 'Go'.
You will see that variable 'lbl_other' defines 'Other'. You can either completely remove word 'Other' in the value field for this variable, so it would not appear at all in the state field for countries without states, or type something else you would like to appear instead of 'Other'. The same procedure should be done for each language in your store if it is multilingual.
Hope it helps.
