Messages format themselves (or have an associated formatter). Queues send messages.
As to the other question, who cares. If there's only going to be one, use a Singleton or static. If you might have different queues (immediate vs. scheduled, maybe, or high vs. low priority, whatever) than instantiate one for each.
Did you look for any open source utilities that do this already?