Both are fine. I think "they trade jokes" sounds more natural, though.

I think they are used differently. To trade jokes implies that you and another person are talking together. One tells a joke and then the other responds by telling one of his own. It's almost a competition. To exchange jokes means to share them. You might just write down or tell some jokes to someone else, for later use, and they return the favor by giving you some jokes. It's more cooperation.