The AI will always attempt to hunt down Gollum if he had been sighted. If you happen to see a few battalions of AI troops randomly moving around and stopping near corners of the map, or in forests, where no enemies are, then it is likely they are searching for Gollum and he was there recently.
You can hear him panting/breathing while invisible, though he does move fast! If I happen to hear him (and you will only hear him if he is in your current screen location, even when invisible) I select a hero at the bottom of the screen and direct them to the location, while moving the screen - following his panting/breathing.
Alternatively using a spell or ability which reveals stealth, such as Sauron's eye or Galadriel's vision will reveal him in the area and allow units to kill him - otherwise you have to be very close to him to break his invisibility.
If Rohan is an AI playing, they will hunt for Gollum just like any other faction, but will not take the ring as the AI does not create Theoden/Grima - so you will have a free run to the dropped ring without any worry of the AI taking it first.