If you can find them on the Gutenberg Project or bartleby.com, you're good.
"Twinkle, Twinkle, Little Star" is definitely PD--it's parodied in Alice in Wonderland, if I remember correctly, and that's well over 100 years old.
Frankly, I wouldn't spend a lot of time researching this. Use the nursery rhymes you want to use, keep a list of them, and note your source for each. When/if you get a contract your publisher will confirm that they are PD or not during the editing process.
TE, "Baa, Baa, Black Sheep" is also public domain. The change to the text in that case sounds like an instance of political correctness....