What is the best way to try and get a referral?

I am currently on my 1 year long job search and have always struggled on reaching/connecting with people on LinkedIn so that I can get a referral. I feel weird just asking, "Hey John Doe could I ask for a referral?" What would be the best way to do that? Also would it be a good idea to apply to some jobs first then tell someone at the company you connected with that you applied or wait for them to refer you? I honestly was never given help at my University Career Center with this, so its all kinda new and a very important thing to learn and do. Any advice or help is awesome.