I may be traveling to Japan on business so this may be very relevant halacha lamaaseh to me.
There are 3 major opinions on where the halachic dateline is.
1. The Chazon Ish, Brisker Rav and others hold that the dateline is 90 degrees east of Yerushalayim. This is based on the Baal Hamaor's interpretation of the gemara in Rosh Hashana 20b. The Baal Hamaor explains that Bait Din has until noon on the day that they see the molad, new moon, to declare Rosh Chodesh on that same day. However, if it is after noon, then Rosh Chodesh is on the next day. This explanation would only make sense if the Halachic Date Line was at the Kitze Hamizrach which is 90° east of Jerusalem. This is so because the reason why the Baal Hamaor said noon is because that is the last time in Israel that somewhere else in the world that the day is just starting. In order for Rosh Chodesh to be on that day, it must be possible for Rosh Chodesh to last 24 hours somewhere in the world. Since noon is 18 hours into the day (starting from sunset on the night before), the place where the day is just starting is 18 hours to the west of Israel which is 270° west of Israel because every time zone is made up of 15°. So, the place where the new day starts, or the Halachic Date Line, must be six hours to the east of Jerusalem which is also 90° east of Jerusalem. This Line is on the 125E meridian (the explanation of the Baal Hamaor is taken from David Pahmer, The International Date Line and Related Issues, The Journal of Halacha and Contemporary Society Number XXI, Staten Island, NY, 1990). This line passes through Australia, China, and Russia. The Chazon Ish writes that all the Rishonim who discuss the topic (the Baal Hamaor, the Kuzari, and others) agree with this opinion.
The Chazon Ish however, throws in a wrinkle. He claims that the dateline doesn't split up a continent and therefore all of China, Russian and Australia, are on the same side of the dateline as Eretz Yisrael, even the parts that are more then 90 degrees east of Yerushalayim. The Brisker Rav disagrees on this point.
As an aside, RHS pointed out that it would seem that the Chazon Ish and Brisker Rav are l'shitasam. The Brisker Rav takes his analysis to it's logical conclusion and that is it. If the Halacha states that on this side of the street it is Shabbos and on the other side it is Sunday so be it. The Chazon Ish on the other hand says that it can't be so (it would be too confusing, people could walk in and out of Shabbos, even skip Shabbos, etc.) and therefore comes up with his chiddush about landmasses. We find a similar machlokes by taking Terumos and Maasros from fruit juice. The Brisker Rav says tough luck, since the halacha states that fruit juice is just maya b'alma you can't take teruma from it so the juice remains tevel. The Chazon Ish writes that you can't have something that is Tevel that has no way to be mesaken it and therefore disagrees.
RHS (and others including R' Sternbuch) point out the following anomoly according to the Chazon Ish. If one is on the East Coast of Australia and sails out to sea on a boat or takes off in a plane on Sunday (anywhere in Australia past 90 degrees), you will sail or fly into Shabbos. The Chazon Ish's chiddush only applies on the continent itself, however, once you leave the continent (either by plane or boat) then since you are past 90 degress from Yerushalayim, you have crossed the dateline and Sunday turns into Shabbos. This has very serious halachic implications for people living in these places with regards to plane and boat travel on Sunday.
According to the Chazon Ish Japan is on the other side of the dateline from EY and therefore what the Japanese call Sunday is really Shabbos.
2. Rav Yechiel Michel Tucazinsky holds that the dateline is 180 degrees from Yerushalayim based on the gemara that states that Yerushalayim is the the center of the world. If so, the dateline is on the exact opposite side of the Earth, halfway around the globe at 144.8 degrees. This places Hawaii on the other side of the Dateline from the United States. Hawaii would then be nineteen hours ahead of NY, rather than five hours behind, as it is on the same side of the Dateline as Asia. The day Hawaiians call Friday is halachically Shabbos, and the day they call Saturday is halachically Sunday.
According to this opinion Japan is not an issue because it is on the same side as the international dateline puts it.
3. Some poskim claim that there is no such thing as a Halachic Dateline. Instead, a person just follows the day that the country that he is in is observing. In other words the halachic dateline is the international dateline. There are other poskim who put the halachic dateline very close to the international dateline (2 or 3 degrees difference).
To sum up, the problematic places are Japan, Hawaii, and New Zealand.
According to the Chazon Ish, Sunday is Shabbos in Japan, according to opinions 2 and 3 Saturday is Shabbos in Japan.
According to the Chazon Ish and opinion 3, Saturday is Shabbos in Hawaii, while according to R' Yechiel Michel Tucazinsky, Friday is Shabbos.
Same as Japan.
Someone I know went to Japan and asked what he should do for Shabbos. The answer he got was to observe shabbos on Saturday, but to refrain from melacha d'oraysa on sunday in deference to the Chazon Ish's shita. This seems to be the consensus of the poskim today.
Some other interesting issues that come up with regards to the dateline are what if you cross the line during sefira, Chanukkah?