In addition to the techniques below, see this roundup of additional explorations of this problem.
Data tables don't do so well with responsive design. Just sayin'.
He has a good point. Data tables can be quite wide, and necessarily so. A single row of data needs to be kept together to make any sense in a table. Tables can flex in width, but they can only get so narrow before they start wrapping cells contents uncomfortably or just plain can't get any narrower.
Responsive design is all about adjusting designs to accomodate screens of different sizes. So what happens when a screen is narrower than the minimum width of a data table? You can zoom out and see the whole table, but the text size will be too small to read. Or you can zoom in to the point of readability, but browsing the table will require both vertical and (sad face) horizontal scrolling.

So here's what we are gonna do...

We're going to use "responsive design" principles (CSS @media queries) to detect if the screen is smaller than the maximum squishitude of our table. If it is, we're going to reformat the table.
We're being good little developers and using Plain Ol' Semantic Markup here for our table. Bare bones example:
<table>
 <thead>
 <tr>
  <th>First Name</th>
  <th>Last Name</th>
  <th>Job Title</th>
 </tr>
 </thead>
 <tbody>
 <tr>
  <td>James</td>
  <td>Matman</td>
  <td>Chief Sandwich Eater</td>
 </tr>
 <tr>
  <td>The</td>
  <td>Tick</td>
  <td>Crimefighter Sorta</td>
 </tr>
 </tbody>
</table>
Our regular CSS is nothing special:
/* 
Generic Styling, for Desktops/Laptops 
*/
table { 
  width: 100%; 
  border-collapse: collapse; 
}
/* Zebra striping */
tr:nth-of-type(odd) { 
  background: #eee; 
}
th { 
  background: #333; 
  color: white; 
  font-weight: bold; 
}
td, th { 
  padding: 6px; 
  border: 1px solid #ccc; 
  text-align: left; 
}
The small-screen responsive stuff comes in now. We've already figured out our minimum table width is about 760px so we'll set up our media query to take effect when the narrower than that. Also, we'll target iPads as they are right in that zone.
The biggest change is that we are going to force the table to not behave like a table by setting every table-related element to be block-level. Then by keeping the zebra striping we originally added, it's kind of like each table row becomes a table in itself, but only as wide as the screen. No more horizontal scrolling! Then for each "cell", we'll use CSS generated content (:before) to apply the label, so we know what each bit of data means.
/* 
Max width before this PARTICULAR table gets nasty
This query will take effect for any screen smaller than 760px
and also iPads specifically.
*/
@media 
only screen and (max-width: 760px),
(min-device-width: 768px) and (max-device-width: 1024px)  {

 /* Force table to not be like tables anymore */
 table, thead, tbody, th, td, tr { 
  display: block; 
 }
 
 /* Hide table headers (but not display: none;, for accessibility) */
 thead tr { 
  position: absolute;
  top: -9999px;
  left: -9999px;
 }
 
 tr { border: 1px solid #ccc; }
 
 td { 
  /* Behave  like a "row" */
  border: none;
  border-bottom: 1px solid #eee; 
  position: relative;
  padding-left: 50%; 
 }
 
 td:before { 
  /* Now like a table header */
  position: absolute;
  /* Top/left values mimic padding */
  top: 6px;
  left: 6px;
  width: 45%; 
  padding-right: 10px; 
  white-space: nowrap;
 }
 
 /*
 Label the data
 */
 td:nth-of-type(1):before { content: "First Name"; }
 td:nth-of-type(2):before { content: "Last Name"; }
 td:nth-of-type(3):before { content: "Job Title"; }
 td:nth-of-type(4):before { content: "Favorite Color"; }
 td:nth-of-type(5):before { content: "Wars of Trek?"; }
 td:nth-of-type(6):before { content: "Porn Name"; }
 td:nth-of-type(7):before { content: "Date of Birth"; }
 td:nth-of-type(8):before { content: "Dream Vacation City"; }
 td:nth-of-type(9):before { content: "GPA"; }
 td:nth-of-type(10):before { content: "Arbitrary Data"; }
}
And so, desktops get the regular table experience, mobile (or otherwise small screens) get a reformatted and easier to explore table:

Hey what about IE?

IE 9 and down don't like you setting table elements as display: block; It does weird stuff and doesn't work right. But IE 9 does support media queries. So my solution thus far is just to wrap the media query styles in conditional comments.
<!--[if !IE]><!-->
<style>
   /* table-related media query stuff only */
</style>
/* Or an external stylesheet or whatever */
<!--<![endif]-->
If the problem was only that older versions of IE don't support media queries, we could use the css3-mediaqueries-js project (polyfills support for all media queries) or Respond (also polyfill, way smaller, but only does min/max-width). They both work very well. But this isn't our problem in this case.
This all works fine in IE 10 and IE 10 also ignores conditional comments, so the styles will work even if wrapped in !IE conditionals.

See it

There are two pages to the demo, one the responsive table solution, and a link to the non-responsive version so you can jump back and forth to see the problem.
In the demo I use a couple of extra media queries for mobile to force the body to certain widths so they don't get feisty. View source to snag.

This isn't perfect...

This is just one potential solution to the problem to data tables on small screens. It's not perfect. There may be some accessibility concerns (or maybe not, I'm really not sure). It's likely there are some fancy JavaScript solutions that could approach things differently and also work great. If other solutions to this come along, I'll keep this page updated.

UPDATE: Other ideas

Scott Jehl created two alternative ideas that are both very cool and very different from this. This highlights an important point: it's all about the specific context of your data table that dictates what solution to go with.
One of them makes a pie graph from the data in the chart. On narrower screens, the pie graph shows and the table hides, otherwise only the more information-rich table shows. Arguably, the mobile version is more useful!
The next idea (Scott credits Todd Parker) is to turn the table into a mini graphic of a table on narrow screens, rather than show the whole thing. This shows the user there is a data table here to be seen, but doesn't interfere with the content much. Click the table, get taken to a special screen for viewing the table only, and click to get back.
Mobile First version by Derek Pennycuff.
Version that starts with divs and the labels are generated by pseudo elements and data-attributes by Mobifreaks.
Generate mobile versions directly (without the div's stuff) from Hannes Kirsman based on this Gist (live demo).