Além de ter uma base teórica sólida, algo que me ajudou bastante a conseguir um estágio foi participar de atividades extra curriculares, como grupos de extensão, empresa júnior e iniciação científica. Isso mostra que de certa forma você conseguiu aplicar algum conhecimento teórico na vida real em casos que você não tem nenhuma experiência profissional.
Outro aspecto que aproveitei bastante foi o contato com alunos mais a frente no curso e também com professores, inclusive o estágio que consegui de primeira foi por uma indicação.
Aprender a se comunicar bem e ter um bom auto conhecimento também me ajudou bastante. As vezes só de você saber se apresentar bem já te coloca na frente de muita gente.
Enfim, no geral com base na minha experiência esses foram os principais aspectos que me ajudaram a conseguir o primeiro estágio.