Regrettably is used when something's a bummer, but it's not necessarily your fault. Regretfully is when you're full of regret, like if you decided to stay home and your friends saw your crush at the dance.
Both words have the same root: regret, meaning to feel sadness, repentance, or disappointment, but they each have their own way of dealing with it. Regrettably describes something that deserves regret, and is used like the word "unfortunately." Regrettably is like bad luck, and it often kicks off a sentence:
Regrettably, Mr. Gao and Dr. Liu's imprisonment reflect the increased assaults on the rule of law and the repression faced by human rights advocates in China. (Council for a Community of Democracies)
Regrettably, some consumer advocates have joined in that chorus. (New York Times)
"Regrettably, few weapons in the history of warfare, once created, have gone unused," Lynn said. (Forbes)
But regretfully is more like a polite way to say sadly, like if you must regretfully decline an invitation to the garden party. Or if you're full of regret, like if you regretfully stayed in on Saturday night because you thought the party would be boring. Regretfully can begin a sentence, but it usually doesn't:
"I am half sorry we spared him after all," Leonidas said regretfully. (Robert H. Fuller)
The man looked down at his boy sadly, sorrowfully, regretfully. (Maurice Thompson)
People have confused them so often, by using regretfully as a sentence adverb to mean unfortunately, that it's kind of okay to do it now. Both words look behind them and wish something else had happened, but regrettably is when it's not your fault, and regretfully is when you're full of it. (Regret, that is.)