My question is how to set up your mxd so that you can use the Query Related Records in REST? Is it as simple as right clicking your feature class, going to Joins and Relate and relate the table that way or am I setting up a relationship class?
Just make both origin and destination layer/table exist in the mxd. If one of them is missing, that relationship will not be advertised by a mapservice.