So I've not been able to find much online about how data should be stored for triangle adjacency.

Currently I calculate my adjacent using half-edges (mention in an answer here).

But do I store this data in with my VBO? (Which means twice the vertex data) Or do I store it in my element array buffer? And if so how do I tell opengl the interleaving I would have in it?

Assuming that each consecutive 3 indices defines a triangle, and that "unsigned *ndx" points to an arbitrary triangle in your buffer, then 6 consecutive indices will define a triangle with adjacency, as follows: