Well, the way it works is this:
The ignition switch has sliding pin type contacts. As you rotate the key, the switch makes the appropriate connections for run and start. When you hit start, it triggers the relay in the under hood fuse box. The relay then powers the solenoid on the starter. The solenoid pulls in and extends the gear drive (Bendix in sine circles). At the same time, the solenoid makes a couple bits contacts inside that directs power from that big battery cable to the actual motor.
If it all happens as per, the engine is rotated.
Since your say it just clicks and doesn't rotate, we'll look at it from that angle.
If your relay is clicking in the under hood panel, your ignition switch is likely good. If it wasn't, at least for "start", the relay wouldn't trigger.
Now you say the starter " clicks". That would seem to indicate that the undehood relay is directing power to the starter solenoid. If you wanted to double check the relay, the ac relay is the same one. Just swap em.
The starter solenoid has two coils. A "pull in" and a "hold". They are both triggered off the " s" wire that comes from the relay. Thus takes a bit more juice than the relay in the under hood panel, that's why the relay is in there: to off load the contacts in the ignition switch.
So if its "clicking" we can assume its making the contacts for the starter motor and engaging the starter gear. If you want to confirm, take the starter out and hook up the "s" wire. It should push out the starter gear. Don't hook up the big battery cable when doing this because the starter will rotate and probably torque right out of your grasp. Alternatively, remove the starter and connect a jumper from the body to the neg post and a jumper from the pos post to the "s" terminal. If the gear pops out, that part of the solenoid is good. Only do thus momentarily or you can damage the solenoid.
If you've gotten this far, reinstall the starter and hook up the big battery cable. Try to start it. Have the inspection cover off so you can confirm the gear engages the flew plate teeth. If it clicks but the motor doesn't turn, you have one of two problems. Then contacts in the solenoid are toast or the battery cable is not getting sufficient contact with the battery to transfer the 100 and some odd amps to turn the engine.
Solenoid is simple: replace it or the starter. You've already done this so it seems unlikely.
Battery cable can be a couple things. Poor contact, corrosion, etc. OEM cables are relatively infamous for building up corrosion inside the formed rubber part where it connects to the battery. Many have peeled it back to find a heck of a mess in otherwise good looking cables.
Thus is about all it can be. The starter circuit is pretty simple really. You can see the diagram here:
http://www.gmtruckcentral.com/wiringdiagrams/1998/Starting-Circuit.pdf