Raid Starships are good, as are high-level bombers, against the superfortresses as well as the regular fortresses. If you put your starting knowledge into one or the other (I usually go bombers), then that should clear it off for you, but at a pretty high cost. Be prepared to send multiple waves against the superfortress, most likely, and also have other ships on hand to protect your bombers from anything else the AI might send to take them out (since the superfortress itself isn't much good against those bombers).
Also, you can use a strategy of misdirectng the superfortress around, if you have to, while you destroy the rest of the planet. If you can survive long enough (leading the SF on a wild goose chase if possible), detroying the guard posts and then the command station of the planet will leave that superfortress without the support of any of the other AI ships, thus making it vastly easier to just whittle down with a bunch of bombers, which are hardly hurt by it at all.
Depending on the strength of the rest of the forces at the planet, taking out a superfortress early in the game is definitely possible, but it's costly and tricky. I usually just try to go around those worlds unless there is something worth capturing on them (as is the case in your situation, unfortunately).
