This can be simple or challenging, the rules are complex and not modernized. In state court, the first step once summons are issued (you supply propsed summons and they issue them officially) is to have the sheriff serve them (cost should be around $40 each.) In federal court, a federal marshall can also serve them for $100; but to my knowledge the sheriff can also serve those for the usual $40 (ask when submitting.) If filing IFP, you may get a free service of parties in state court by sheriff or in federal court by federal marshalls; but federal court won't give free sheriff service (and federal marshalls only serve for federal court.
In a residence, the party or anyone 15+ residing there can accept service in my state (probably yours), you can serve their spouse sometimes; in an office it has to be the person except some narrow exceptions that allow serving the owner of the business (sole proprietership, implies the person you're serving if that's their employer; I'd need to do further research but it's so narrow it won't work usually) and if it's the registered agent for a government agency then after 1 attempt they can serve someone working there.
In state court (my state at least, double check your state) you have 120 days to serve parties, with a possible 30 day extension. In federal court, you have 90 days to serve parties and they're more strict about it.
Federal court has service waivers, if service is waived; the defendant gets an extension to respond and if they don't waive service within 21 days of receiving it they may be held responsible for the costs of getting them served. State courts have started allowing service waivers, check to see if your state is one of them.
If service attempts fail and they don't waive service, you have several options. One note, if working pro se then private service processors may not be allowed to do a skip trace that they can do for a lawyer or law firm. If you have an address, you may be able to confirm it with the DMV by filing forms or an affidavit stating this is for serving a defendant in a lawsuit; depends on state regulations.
Private servers can be as cheap as $76, a skip trace may be an added fee if they can do it. Some independant process servers have PI licenses which may allow them to do the skip trace for a pro se party.
For state court, after the first service attempt I'd try a service waiver; if that doesn't work try an alternative address and maybe a private server at the primary address before motioning for alternative service. I'd motion about day 65.
In federal court, you're on a strict deadline; start with a service waiver that brings you to 21 days. If they don't waive service, try all addresses you have at once (let's say $40 for both) and that brings you to 35 days, then try a private process server which brings you to 49 days. At that point, I'd motion for alternative service. Whether they'll extend isn't as clear upon further search, a judge may have that right at their discretion, but assume a strict deadline and motion for more time if needed.
Alternative Service The bad news is, most lawsuits the court won't let you simply post in a newspaper (only allowed for very narrow cases) or serve their secretary or even counsel (you'd think someone has representation, the court would consider that proper service) and even government officials can't simply be served on email addresses or certified mail they surely had access to. Alternative service is regulated, a judge has to go by statute. If someone evades, the judge can give alternative service of serving the secretary of state for your state in state court if your state has adopted that. In federal court, they usually go by the state rule which is the secretary of state for your state (double check to make sure this is true for your state.)
If everyone is not served yet, make sure to motion for an extension; even if the judge has already approved the motion for alternative service. Motioning for alternative service around day 49 in federal court and day 65 in state court, motioning for an extension in state court at day 85. Don't stop until both parties are served.
Final noteYou can't serve people on sunday for some reason, you can't serve them on the way to/from or at court, they have to be served between 7am and 9pm. Double check these with your state, but they should be right. For home service, sheriff is good because they're more credible in evasive service "party ran inside, I saw them, it's John Smith" is more credible from a sheriff than a process server. Sometimes non-parties who are 18+ can serve or get licensed to serve, but if allowed; their service may face more scrutiny if disputed.