Don't worry Jen, you are not alone. I have been in the UK for almost three years and I have never worked full-time. At first, I found it quiet daunting applying for jobs and taking time to rewrite CVs and covering letters without even getting any reply. I worked as bar staff (part-time) for more than a year while studying.
If you are keen on getting some experience in the UK to boost your CV, you can look into volunteering. There are a lot of charitable organisations who are in need of volunteers. It is also a good way of networking - I met my ex-boss while volunteering in a local charity shop and he offered me the job.
I now volunteer with three local charities to get some office experience - I still do not know if it will pay off. One can only try. With regards to registering with recruitment agencies, it might be a good idea to call them and ask if you could pop in for a chat or leave your CV. Good luck in your job search. You will find one in time.