Im using Frontpage to build my website, does every host work with frontpage? Or do I have to find one that works with it, cos I see things on some hosts that say frontpage extensions or something like that.

Not all of them work with frontpage, usually they will list that kind of stuff in their faqs.

All hosts work with Frontpage. However, Frontpage Extensions will only work on a server that supports them (see Rosey's post).