Gävle Bro is the place to go. Take bus number 2 or 4 towards Andersberg. Get of at the stop Ramna after about 15 minutes or so. Gefle Forum is the stop before so just sit in the front of the bus on the right side. When you get of at Ramna you will keep going straight on the road where the stop is. The bus will turn left but you keep going straight and after maybe five minutes you will see the sign for the Gävle Bro highway rest stop, then it's maybe five more minutes walking. This place is great to catch a ride north or south on the E4 It sees traffic not just from the highway but also leaving the town itself. Cars stop on both sides for food and gas and so just ask people if you can go whit them. If going south you should not accept a ride shorter then Stockholm.
Please if you know update and let us know. But from what I know its hard. You can stand whit the thumb on the bus station before the circulation where the E16 starts but it might take you a while to get a ride... Bus number one direction Valbo takes you there,
Places to avoid
Accommodation and Sleep
Other useful info
Buses in Gävle wants you to pay whit card and cash is mush more expensive.