Over the years, the question of when one can start using the fruit on their newly planted tree arises so it is worthwhile to summarize the halacha l'ma'aseh for this. On one hand the Mishna says that the first day of Tishrei is Rosh Hashana for new plantings, yet we say Tu B'shvat is Rosh Hashana for trees. Both are true.
Replanting potted trees:
Any fruit that grows on a tree for the first 3 years has a status of orlah, and during the fourth year has a status of נטע רבעי. The count begins from when the tree is planted, but if the tree is uprooted and replanted, it is complicated because one must determine if the dirt that was removed with it and how long it could have lasted. The Shulchan Aruch (294:19) writes that if it could survive with the dirt that was removed with it without adding any additional dirt, the count need not restart. However, often the tree can be uprooted and replanted in the pot that already contains soil. In that case the count would at least restart from the point that it was potted. If it is then removed from the potted soil and placed into the ground without much of the potted soil, the count would restart once again. It is not clear in the Shulchan Aruch how long it would need to survive in the dirt that was removed with it. The Pischei Teshuva (13) sites an opinion of the פרח מטה אהרן who says that it has to have enough dirt to survive for the duration of the years of orlah, 3 years. The Pischei Teshuva also quotes the Livushei Sered as saying that the Shulchan Aruch doesn't permit one to actually replant a tree with dirt to avoid the orlah years, it is only bidieved. He also writes that it is not so clear how much dirt it would need to survive for all 3 years. The Shivas Tziyon disagrees and holds that only in Eretz Yisroel would we require enough dirt to survive for 3 years, but in chutz la'aretz even if it is uprooted with just enough dirt to survive for days, it is sufficient. Furthremore, since we pasken that safeik orlah in chutz la'aretz is permitted (even though it is d'oraysa, it is part of the halacha l'moshe misinai to be matir the safeik), if one is unsure it is permitted. Based on this, one can generally be lenient in chutz la'aretz and assume that there was always enough dirt both when removed from the ground originally and when replanted, surrounding the roots to survive for a few days. Therefore, one can judge the age of the tree by its size and maturity to determine whether it is still within the years of orlah.
Rules of Orlah and Revai:
The fruits of orlah that grow within the first 3 years are forbidden to benefit from. The fruits which were orlah will always remain orlah regardless of how much time passes. Orlah is not a דבר שיש לו מתירין since the fruits that are assur will never become mutar. The fruits that grow during the fourth year have status of נטע רבעי. Nowadays when there is no option of eating the fruits in Yerushalayim, they can be redeemed onto a coin and are permitted. One should not redeem the fruits until they are detached from the tree (Shulchan Aruch 6 and Shach 11). One can redeem even a large quantity on a peruta and deform the coin afterward. There is a bracha made on the pidyon - על פדיון רבעי. There is a machlokes cited in Shulchan Aruch (7) whether netah revai applies in chutz la'aretz. Rabbeinu Yona holds that it applies in chutz la'aretz as it does in E.Y. The Rambam holds that it only applies in Eretz Yisroel, but in chutz la'aretz the fruits are considered chulin after the 3 years of orlah and there is no need for redemption. Other rishonim (cited by the Rama) holds that it applies to grapes in chutz la'aretz but not to other trees. The Shach (17) seems to hold that for all trees in chutz la'aretz one should redeem the fruits without a bracha. However, the Gr"a (28) says that the third opinion is the ikar and therefore in chutz la'aretz one can be lenient to use all fruits other than grapes after the 3 years of orlah have passed without redeeming.
Counting the years:
The system for counting the years of orlah is relatively simple. It takes 14 days for the tree to take root (in halacha), and must take root 30 days prior to Rosh Hashana to count as the first year. Also, Tishrei is the Rosh Hashana for newly planted trees, whereas Tu B'shvat is Rosh Hashana for full grown trees. Therefore, if one planted a tree 44 days before Rosh Hashana (before 16th of Av), those 44 days count as year one. From tishrei to tishrei ends year 2, and from that tishrei to the next tishrei ends year 3. BUT the fruits at the end of year 3 remain assur until Tu B'shvat because at this point we regard it as a full grown tree so that the Rosh Hashana is 15th of Shevat, not Tishrei. Therefore, the fruits that reach the stage of חנטה prior to Tu Beshvat of that year remain assur forever, but the fruits that are only cho'neit after Tu B'shvat are permitted to be used. There is a machlokes Rishonim whether the requirement to wait until Tu B'shvat is due to the fact that we are cutting corners at the start of the count and considering anything more that 44 days prior to Rosh Hashana to count as a year. The opinion of many Rishonim including Rashi ("ד"ה ופירות - "מט"ו בשבט עד ראש השנה - משמע שודאי מותר בר"ה הרביעית) and the Rambam is that if one plants within 44 days of Rosh Hashana so that their first year will only end after a full year plus, they can use the fruits that are cho'neit at the end of the third year and don't need to wait until Tu B'shvat of that year (the Yerushalmi Shevi'is perek 2 end of halacha 4 says this almost explicitly as the pnei moshe explains). The Ran disagrees and says that even if one is waiting a full 3 years or more, only fruits that reach חנטה after Tu B'shvat are permitted. This argument would only apply if one actually waited 3 full years, meaning 3 Rosh Hashana's have passed, but if one planted a few months prior to Rosh Hashana and are considering those few months to be the first year, all agree that they would have to wait until Tu B'shvat after the passing of the third Rosh Hashana (Shach 11). In chutz la'aretz one can certainly be lenient so that if 3 Rosh Hashana's passed the fruits that are cho'neit from that point and on are permitted. Furthremore, even if one knows that the tree was planted in the summer (if they didn't even know if it was planted in the summer, they can certainly assume it was planted more than 44 days before R.H.), but couldn't recall whether it was prior to the 16th of Av, they can be lenient in chutz la'aretz to assume that it was planted early and use the fruits that are cho'neit after Tu B'shvat of year 4 (Shivas Tizyon cited by Pischei Teshuva 3).
Trees from a non-jew:
Orlah applies m'doraysa both in Eretz Yisroel and in Chutz La'aretz, just that in chutz la'aretz it is a halacha l'moshe misinai which includes that special exemption for ספק ערלה. It even applies to property that is owned by a non-jew. Therefore, one cannot purchase fruits from the market if there is a strong chashash that they are orah fruits. The Chasams Sofer (cited in Pischei Teshuva 7) holds that the combination of factors, chutz la'aretz and land of a goy makes it so that the orlah is only d'rabonon.