IIRC, the Dutch appear like clockwork in 1561 in the SJ campaign, somewhere on the map in the west. Not sure about the added campaigns in WE. if you're playing an Eastern faction however, you won't likely see them until much later.

I did a quick search to see if anyone else noted the date the Dutch arrive and found these:

http://www.gamefaqs.com/pc/451526-sh...ion/faqs/21099

Search on 1561 within the document to find the statement.

This, I noted, is hosted on the Mizu server somewhere:

http://files.mizus.com/files/STW_WE/.../Preview2.html

So I think it's a safe bet to assume that the Dutch arrive in the game somewhere in 1561, though you might not see them until later depending on what clan you are playing and where your empire is on the map.