The 6 x 6 posts are all attached to concrete footings using the typical Simpson style post base connectors. I am looking for options on how to correct the problem. I have considered simply bolting or nailing a 2 x 6 to the side of each post under each beam but I am hoping there is a simpler, less kludgy solution.
If the deck is 2' off the ground or less, I wouldn't be overly concerned about it. Otherwise, if they are already existing the easiest way would be to use hardware designed for this kind of connection.
Keep in mind that a beam that consists of two 2-bys means the two 2-bys are sandwiched together and nailed together so they share their loads and reduce twisting, deflection, etc...
This means that your beam might not actually be properly size either, which is not a problem a bracket can fix for you. You might need a bracket AND more 2-bys. That or just redo it properly instead of trying to fix it.