Yes, this is quite possible. I've made tons of skins while using the grid system. After you've included the grid CSS in the skin, go through the layout.master and add the grid classes you need.
For elements that aren't in the layout.master, look in the theme.skin. You can add grid classes to almost everything there, primarily the layout panels (center, left, right), and the divs that the modules use (like the blog, you can put grid_8 on the post wrapper and grid_4 on the blog navigation, etc).
Hope this helps,