How did Darth Maul know that Amidala was on Tatooine?

Question

After evading the Trade Federation blockade, Padmé and her chums make an emergency landing on Tatooine. Sidious and Maul are hunting for them and appear to use a transmission from Sio Bibble as bait to get her to respond. Obi-Wan immediately spots that it's a trick and he and Qui-Gon are equally emphatic that no reply be made because it could cause a "connection trace" that could be used to track them.

BIBBLE: ... cut off all food supplies until you return.. .the death toll is catastrophic.... we must bow to their wishes, Your Highness.... Please tell us what to do! If you can hear us, Your Highness, you must contact me....
OBI-WAN: It's a trick. Send no reply.... Send no transmission of any kind.

INT. ANAKIN'S HOVEL — MAIN ROOM — DAY
QUI-GON listens to his comlink. OBI-WAN is in the cockpit.

OBI-WAN: ... the Queen is upset... but absolutely no reply was sent.
QUI-GON: It sounds like bait to establish a connection trace.
OBI-WAN: What if it is true and the people are dying?
QUI-GON: Either way, we're running out of time.

In the very next scene, however, we learn that Maul and Sidious have still managed to trace them.
How was this accomplished? Did the Queen respond without telling the Jedi?

Answer 1

According to the, now Legends, novel The Wrath of Darth Maul, Darth Maul sent out the distress signal and the Queen did respond so that he could establish the trace. So according to this he traced them because they actually did respond even though the film kind of skips over this.

Maul’s plan was to transmit the message and establish a connection trace to pinpoint the location of Queen Amidala’s starship. He routed the transmission so it would appear to originate from the Royal Palace on Naboo. And then he waited.

It did not take long for Maul to intercept a response, a brief encrypted message that said the Queen was safe and would soon return to Naboo. The response came from a small sand planet in the Arkanis sector, in the Outer Rim Territories. The planet’s name was Tatooine.

_{The Wrath of Darth Maul}

In another now Legends novel, Darth Plagueis, it is stated that after sending the message a connection trace was established. It doesn't make it clear if this is because of a response or just because the message was received, however.

The invasion and occupation of Naboo were proceeding on schedule, and the swamps were being searched in an effort to locate and isolate the principal underwater habitats of the planet’s indigenous Gungans, before they could pose a threat. But the two Jedi, Queen Amidala, and her retinue of body doubles and guards had succeeded in blasting their way through the blockade. With Maul’s help, counterfeit messages from the Queen’s adviser Sio Bibble had been transmitted to the missing starship, and one transmission had returned a faint connection trace to the Hutt-owned world of Tatooine. On learning as much, Plagueis had considered asking Jabba to apprehend the Queen, but not for long, out of concern for what the dark side might demand of him in return.

“Tatooine is sparsely populated,” 11-4D said, repeating what the Dathomiri Zabrak was saying to Sidious. “If the trace was correct, I will find them quickly, Master.”

_{Darth Plagueis}

Answer 2

The implied answer seems to be that the Force assisted Maul in his search.

Nute Gunray: My lord, it—it's impossible to locate the ship. It's out of our range.
Darth Sidious: Not for a Sith.
...
This is my apprentice, Darth Maul. He will find your lost ship.
Nute Gunray: This is getting out of hand! Now there are two of them!
Rune Haako: We should have not made this bargain.

The Trade Federation had ample technical capabilities, and I think it is reasonably to believe that if their ships (which were right there on the scene as Amidala's vessel vanished into hyperspace) were unable to track her ship, then it was not possible to do so via standard (technological) methods.

However, we also know that a Sith's Force sensitivity can be an extremely useful augment to traditional methods of search. In The Empire Strikes Back, Vader's taskforce sends out a fleet of probe droids, searching for evidence of the Rebels' new outpost. As Admiral Ozzel points out, "There are so many uncharted settlements," at the fringes of the galactic civilization. But Ozzel is a mundane, whereas Vader has the power of the Force. Once the probe brings Hoth to Vader's attention, the dark lord immediately knows that it has found the right location.

Later in Empire, the imperial fleet, believing the Millennium Falcon has gone to light speed, makes an inventory of possible destinations along the ship's last known trajectory. Presumably, Maul could do something similar and whittle down the number of planets that Amidala might head for to a reasonable number. Then, with his Force intuition, he could pick out Tatooine as the correct (or, at least, most likely) landing site for her ship.