Do both mean exactly the same or do they have slightly different meanings?
Personally I would put more of a regular scheme to frequently, as the word comes from the same stem as frequency (a sine curve of certain wave length, therefore repeating itself in a certain pattern). Often would denote more of an irregularity.
Maybe this is a déformation professionel, as I am programmer with a math background, or I derive it from German and Latin languages, for example French:
fréquenter quelquechose would mean to regularly go somewhere.
Therefore I would hear this
- I frequently go to the gym - usually I go there several times a week on the same days each week
- I often go to the gym - I go there as often as I can, but can't keep a clear schedule
First of all, although the meaning is essentially the same, to the point of one being used as a definition for the other in some dictionaries, often is an order of magnitude more common than frequently. Secondly, they occur together (collocate) with different words.
I can't see a clear semantic pattern to the collocations, but it does seem that the strongest collocations for frequently also commonly co-occur with often, but the strongest collocates for often usually don't go with frequently. This suggests that often has a broader meaning that includes frequently but goes beyond it.
In colloquial English, they mean the same thing. Remember the pun in The Pirates of Penzance (which only works in British English): "When you say 'often', do you mean 'often' 'someone who has lost his parents' or 'often' 'frequently'?"
If there is a difference, it is that "frequently" describes a periodic relationship with an ongoing action, while "often" means a lot of times during the defined period. In effect, it's the same thing, just a very slightly different flavor.
They have the same meaning: