I was in the same boat as you are about 10 years ago... There was barely anything on the internet, but persistence paid off and over the 10 years I have found sites here and there that have helped me get to where I am today. I started with just up to my great grandparents and today I have gone as far back as the 1500s!
I actually came across this post as I haven't 'googled' in a while to see if I can find something new on the ancestors.
Anyway, I have a blog where I record my journey and I have a page with a list of sites I found useful along the way: https://missmalta.wordpress.com/links/ Feel free to check it out... When I first started and persisted, I used to come across a couple of blogs that inspired me to keep going, so hopefully, mine might just do that for you. The links page though, I think you will find very useful.
In answer to your question though... If you are wanting just some names to climb up the tree, if you know your grandfather/great grandfather's name(s) and DOB, you can order their birth/marriage/death certificates from this site: https://secure2.gov.mt/certifikati/department.aspx on the certificates they will have the parents names and their occupation... That will then give you a lead to go back further up the tree.
Also, as others have suggested, speaking to any living relatives that may have any information to help you go back is a BIG help. Names, DOBs... Anything - this will assist immensely!
I didn't get too far with this because unfortunately, they won't have the DOB of the parents on the certificates. And my grandparents have all passed away, my parents didn't have too much info that could help me. When I visited Malta I went to the village church and they had record of the births/marriages/deaths. From there we kept going back.
With all those names I could then sit on the net and google each name til I got a lead... Which I did and the things I found were mind blowing!
Now if you aren't visiting Malta anytime soon, you could do 2 things;
- Get in touch with a Maltese genealogist (I live in Australia, I know of one I can recommend here, there's another one in Malta that I can suggest) or
- Email the Public Registry in Malta (or Gozo specifically if your family is from there) and they may be able to assist. Email them as many details as you can give them and they should be able to put you into some kind of a lead.