Does this plugin work with any Theme?

Yes it does, you only have to install Woocommerce Plugin first.(It can be downloaded from here : http://www.woothemes.com/woocommerce/ )

It works with any Wordpress standard themes or custom Woocommerce themes.