Pretty self-explanatory. When I restart my Rust servers on my Linux Debian box, they don't automatically start. Do I need to add something to my startrust.sh file that tells it to automatically start upon shutdown? (shutdown of the rust server, not the box itself)

My startrust.sh

You would need an external tool or script; the server cannot start itself.

How would I go about doing that? How would Linux detect when to run startrust.sh? How can I tell it to run it automatically after the server is shut down?

The usual method is a cron job.

Depends HOW you are running RUST to start with...........
pls show the command you would normally start the system with for the first time.......

Also a bit more clarification on restart
physical server or just RUST instance....

options I might use (server hard restart):
1. systemd

Rust "restart"
"--restart unless-stopped"

I'm running rust with the sh script pasted above with Pastebin. (https://pastebin.com/ByWT645a)

I'm talking about just the rust instance restarting, not the physical server. 

What do I need to do? I'm confused by what you said. 

SmoothRestarter seems to do the trick

Hes all sorted out & a happy bunny now.......

How did he resolve the starting issue in the end? SmoothRestarter plugin won't do that.