Beside the obvious - building Outposts and Colony-ships, what other options are there to expand the borders?
There are a number of technologies you can research that increase the size of the borders around your outposts and colony ships, including
Propaganda Transmissions (Repeatable)
The Stellaris Wiki entry on borders also says that:
Border spread appears to work volumetrically. That is, as the empire becomes more dense and grows, its borders also appear to spill outward. Removing colonies or frontier outposts from within the empire's well-established borders may affect the outer border unpredictably.
So building additional colonies and outposts in your empire's interior can increase your borders at the fringes.
If you're expanding your empire via frontier outposts, it's worth noting that
Outposts controlled by sectors do not cost Influence to maintain.