Will a square and octagon tessellate together?

The angles of a n-sided regular polygon have the measure of (n-2)*180/n degrees.

A regular octagon's angle has (8-2)*180/8 = 6*180/8 = 135 degrees.

If you stick together two sides of two different (but congruent) regular octagons you get one downward and one upward. We can say this without loss of generality because up and down are just perspective that you can change as you look around the construction.

So, at the left of the common side you have two angles around the vertexes. Both of the angles have 135 degrees (being angles of regular octagons). But there is a third angle. The sum of the measures of angles around a point is 360 degrees. So the third angle has 360-135-135 = 90 degrees. And the two sides that form the angle are congruent. ==> you construct a square.