If you don't want the leading zero, then you only need the digit 0 on one of the cubes so you can represent 10, 20, and 30. Create one cube with (1,2,3,4,5,6) and the other with (0,1,2,7,8,9) and you can represent any date from 1 to 31 (well, really 32).
If you do want the leading zero, you need to have a 0 on both cubes to represent each date from 01 through 09. However, this presents a problem: You need 0, 1, and 2 on each cube, but that only leaves room for six more digits, and there are seven left to place (3 through 9). The trick is to note that 6 and 9 look pretty much the same when turned upside down, so you can omit one of them and turn the cube over to represent either one. So, you have cubes with (0,1,2,3,4,5) and (0,1,2,6,7,8).
Because I lack the woodworking tools to make a nice set of date cubes out of something durable like wood, I opted for something a bit less durable: Paper plus inkjet printer. I also took this as an opportunity to learn something about creating Postscript by hand (it's not that bad really), and came up with datecubes.ps which you can print, cut out, fold, and paste together. If you're on a Mac, then the Preview app can handle Postscript files natively, otherwise you'll have to use something like GSview to print/view it.
Update: I'm feeling nice so I made a datecubes.pdf for anybody who finds plain Postscript files awkward to deal with.