How can I create a staggered, repeating procedural pattern?
Here are the nodes for creating staggered texture mapping for procedural textures.

First the Y axis gets multiplied by the number of lines you want to have in the pattern (the Lines value node).  After adding .5 that gets rounded creating stripes (along the X axis in this example). 


If you were to look at the output from that node at this point it would look all white, that is because the values start at 1 and increase by 1 with each stripe.




The next three nodes take the stripes, multiplies it by the reciprocal of the input value (lines), then by 0.5 to lower the values. Then the X axis is added in.

At this point there are only stripes, next the Modulo math node causes the texture coordinates to repeat.
All that was for the X axis.

The Y axis is simple, it is just the Modulo of the reciprocal of the lines.

With the nodes pictured at the top you can get a pattern like this.


After adding the Subtract and Absolute nodes from Jerryno's answer,  every other tile will be mirrored and you can get a pattern like this.


This blend has the nodes packed in to a node group, which can easily be added to any project.

Blend File

As you can see, manipulating the texture coordinates of generated textures is quite powerful.