attatched is more info about the starting system than you probably wanted to know. I would do some diagnostics before going out and replacing anything because most of these components are pretty pricey. If you are familier with basic electronics and the operation of a relay it shouldn't take you more than an hour or two to pin down the problem. A solonoid and realy are essentially the same thing in this case. I would start with the easy stuff first, the clutch switch and the relay. Fortunatly because of the amount of current involved the starting circuit has to be pretty simple.

info is from the 98-01 FSM but should still be applicable.