Thanks for the help everyone.
Firstly, do you know how the relay is wired up?
Are you controlling the circuit between the power + and the relay, or between the relay and - ?
If the former (which is most likely), then you really need a P channel MOSFET, as that is much better at high side switching.
Here is the schematic from the generator. I highlighted the two wires I'm tapping into for the remote start (red and red/white). From what I can tell, I'm controlling between the power and the relay, as Chagrin stated. I did test this with a relay and got everything to work. I wanted to use a MOSFET due to space constraints and I thought it was a simple swap.
So I need a P channel instead of the N channel that I have? I'll look into that. If anyone has any good links for tutorials, I appreciate it.

Do you have 0 volts on the Arduino going to 0 volts on you controlled circuit?
Yes, they are all grounded together. This is easy since I'm powering the Arduino off the generator battery.
You will need a flyback diode across the relay winding to prevent inductive spikes damaging the MOSFET.
I thought that was only needed if the MOSFET was controlling something with a winding like a motor. Since I'm controlling a relay, I thought the diode wasn't needed.