@Mark
The things is that Denmark is so small that we can’t have everything translated in to Danish, so most people will know at least a little English. Of course the older part of the population aren’t fluent at all, but the younger generations are generally pretty good at English.
So to answer your question, fluency is not common and will mostly be attained by businessmen and the younger generation. Most Danes do however understand and speak English just fine – though not at a level that I would consider fluent.
Also I don’t know if it is right to refer to myself as fluent, I don’t know when you are eligible for that title…