It depends on several things. The basic tile size is 32px, but quite often I use 16px. I find that if I'm designing something for mobile, then 32px is too large, but for a flash or desktop game, it would be fine.
Best thing to do would be to mock up the levels and see how they look. Maybe even create a basic level in stencyl to test out how it works?