Yes. Getting verified will help.
Also, usually, a celeb's twitter account will be up in the first page of search most often.
If you just type in the celeb's name, their twitter account will appear towards the top. If that celeb doesn't have a website, IMDB page, or any current news, usually twitter would appear at the top.
Other than that, most of what trends on twitter appears high on google searches, so if the celeb does something newsworthy (drops an album, drops a baby, etc) then google search will pick that up.
I used to follow SEO for social media around the time that google said they'd include twitter and facebook in searches... but, I think google ratcheted it down.
I really think the best way is to simply put the twitter account link on high quality websites (good ol backlinks)