Egypt and Tunisia have both taken steps to form a new government after the overthrow of Mubarak and Ben Ali respectively.
In this context, does respectively describe the steps that have been taken, or the overthrow of Mubarak and Ben Ali?
Respectively shows that Egypt has taken the steps mentioned after the overthrow of Mubarak, and that Tunisia has done so after the overthrow of Ben Ali.
As for your headline question, adverbs can modify verbs, adjectives and other adverbs, as well as a number of other word categories.
Adverbs do a lot of jobs. In this case though it is affecting the verbal phrase "taken steps to form a new government". It means that they have carried out that action in a relative manner.
Consider if we were to replace it with the adverb together. This would mean that they had acted with each other on the action "take steps to form a new government" (it would be an awkward but valid meaning). Or with the adverb rapidly, again it would affect that verbal phrase (and again it would be awkward and graceless to have the adverb so far from the verbal phrase without a good reason, but it would be valid).
More generally, adverbs can modify verbs, adjectives, other adverbs, entire clauses, entire sentences, and just about anything except determiners and nouns.
Shall I say 'adverbs can't modify adjectives and other adverbs...'? Or 'adverbs can't modify "just about anything except determiners and nouns" '?
No, because those who subscribe to the traditional, broad-brush approach would not like it. However, neither do I like the implicit claim that the traditional approach is gospel here. (Though I do think that the total ditching of word-classes, recommended by some, would deprive us of a valuable analytical tool.)
I'll just quote from an approach I consider to be an attempt at a far superior analysis ( https://www.sussex.ac.uk/webteam/gateway/file.php?name=essay---parts-of-speech.pdf&site=1 ) :
In every language, almost all of the lexical items fall naturally into a small number of classes, and the words in each class behave grammatically in much the same way. Linguists often call these classes word classes or lexical categories, but the traditional term is parts of speech.
The ancient Greek grammarians recognized eight parts of speech for their language. The Roman grammarians who followed them recognized a slightly different list of eight classes for their own language, Latin. Over the centuries, European grammarians proposed several different lists for English and other languages, though curiously the total number of classes recognized was eight in almost every proposal. By the early twentieth century, grammarians of English had agreed on a set of eight parts of speech: noun, pronoun, adjective, verb, adverb, preposition, conjunction and interjection. This list of categories became the orthodox view of English and of other languages, and it was almost universally taught in schools in the English-speaking world, until the teaching of English grammar began to be abandoned in the 1960s.
This set of eight classes is still taught in those schools which teach any English grammar; it is found in many grammar books of English (and even in one or two textbooks of linguistics); and it is the list used by many dictionaries of English in assigning part-of-speech labels. But it is grossly inadequate.
English has at least a dozen parts of speech, and trying to squeeze all these classes into just eight is a serious error. The traditional classification lumps together classes of words which have little or nothing in common and which simply cannot be sensibly forced together. In particular, the traditional classification abuses the category adverb: practically every word which fails to fit sensibly into one of the recognized categories is shoved absurdly into the “adverb” box. As a result, you should be very cautious about accepting the part-of-speech labels given by dictionaries and traditionally-oriented grammar books. In particular, you should be wary of the label “adverb”.
[bolding mine] The article suggests about 15 possible classes, and is well worth reading, though I'm sure the authors wouldn't claim it to be the finished article.
I'd class respectively above as a pragmatic marker subclass text organiser - relating. It does not add material to the proposition contained in the sentence proper, but makes sure that information is understood correctly - as is said above, the word may be omitted if the audience doesn't require the additional structuring.