I always thought the song was about the tv ads for the british army ...when it was originally released i think things were pretty bleak on the work front. There used to be a poster sending up the recruitment campaign with something like: Join todays army, travel to far off places, meet interesting people and then ...........kill them....
Or perphaps he was using Oliver (Cromwell) as a way of avoiding saying the british army.
Info from the Elvis Costello homepage: http://www.elviscostello.info/faq/lyrics.html
Oliver's Army - About the invasion of Ireland in 1649 led by Oliver Cromwell, and modern British occupation of N. Ireland.