On the bigger sites you will absolutely need a CSCS card (blue for level 2, gold for level 3) together with basic PPE (boots - many sites insist on S1P or S3 as they have sole protection, hi viz, hard hat, etc).
To get a CSCS card you'll need to do the H&S test (£21 if you apply directly to the CITB - avoid third party firms to book the test as they will just rip you off) then apply for a card (£36, again direct from CITB CSCS - needs proof of relevant NVQ and passport photo, takes a couple of weeks although many places will let you on if you have a copy of the test pass sheet and can show that you've applied for a card). Don't be tempted to go for a green (labourer) card - you now need to do a 1 day course as well as the H&S test before applying for a green card (which costs a lot more than just getting a trade card) and more and more bigger sites are refusing to take trades who turn up with a green card.
CIS is no longer a card - just ring Customs & Revenue and request your UTR (unique tax reference) which will take them a couple of weeks to post out to you.
And yes, a lot of work these days is through agencies who will pay you through a payroll company, but avoid any that want to put you through an umbrella scheme (unless you thoroughly investigate it - it's all too easy to get rinsed) and any that insist you go PAYE only. Expect to pay £25 to £20 a week (this is deducted pre tax) for the services of the payroll firm. The one good thing you can say for these arrangements is that you get paid a week in hand by almost all of them and that if the client goes belly up you are still going to get paid.
Good luck!