Sachverhalt:
A.
Die Eheleute A._ und B._ geb. C._ (im Folgenden: die Steuerpflichtigen) meldeten sich per 1. April 2012 in der Gemeinde U._/LU an und von dort per 1. April 2013 nach Conceição (Portugal) ab. In Portugal halten die Steuerpflichtigen seit 1996 ein Einfamilienhaus und in U._ eine 4.5-Zimmer-Mietwohnung, die sie auch nach ihrer Abmeldung weiter benutzt haben. Die beiden Wohnstätten in Portugal und in U._ stehen im Eigentum der X._ AG, deren Verwaltungsratspräsident A._ ist.
B.
Die Gemeindeverwaltung U._ teilte den Steuerpflichtigen am 13. Juni 2013 mit, dass die Einwohnerkontrolle eine rückwirkende Anmeldung ins Steuerregister per 1. April 2013 vorgenommen habe, da die tatsächliche Anwesenheit und der Lebensmittelpunkt der Steuerpflichtigen in U._ zu bejahen sei. Da die durch die Gemeindeverwaltung geforderte Wiederanmeldung nicht erfolgte, erliess das Steueramt U._ am 4. März 2014 einen Feststellungsentscheid und erklärte die Steuerpflichtigen ab dem 1. Januar 2012 in U._ unbeschränkt steuerpflichtig. Die dagegen von den Steuerpflichtigen erhobenen kantonalen Rechtsmittel blieben erfolglos (Einspracheentscheid der Dienststelle Steuern des Kantons Luzern vom 28. April 2015 sowie Urteil des Kantonsgerichts Luzern, 4. Abteilung, vom 24. April 2016).
C.
Mit Eingabe vom 30. Mai 2016 erheben die Steuerpflichtigen Beschwerde in öffentlich-rechtlichen Angelegenheiten beim Bundesgericht. Sie beantragen, der angefochtene Entscheid sei aufzuheben und es sei festzustellen, dass die Beschwerdeführer ab 1. April 2013 nicht mehr in der Schweiz steuerpflichtig seien. Eventualiter sei die Sache zur Neubeurteilung an die Vorinstanz bzw. das Steueramt zurückzuweisen.
Auf die Anordnung eines Schriftenwechsels wurde verzichtet.

Erwägungen:
1.
1.1. Es rechtfertigt sich, die Verfahren 2C_510/2016 (Staats- und Gemeindesteuern) und 2C_511/2016 (direkte Bundessteuer) zu vereinigen. Ihnen liegt derselbe Steuersachverhalt zugrunde, es stehen sich dieselben Parteien gegenüber und die aufgeworfenen Rechtsfragen stimmen in einer steuerlich harmonisierten Materie überein (vgl. <ref-law> i.V.m. <ref-law> [SR 273]; <ref-ruling> E. 1 S. 60 f. mit Hinweis).
1.2. Die Beschwerde in öffentlich-rechtlichen Angelegenheiten ist gemäss <ref-law> in Verbindung mit Art. 146 des Bundesgesetzes vom 14. Dezember 1990 über die direkte Bundessteuer (DBG; SR 642.11) sowie Art. 73 des Bundesgesetzes vom 14. Dezember 1990 über die Harmonisierung der direkten Steuern der Kantone und Gemeinden (StHG; SR 642.14) zulässig. Die Beschwerdeführer sind gestützt auf <ref-law> zur Beschwerde in öffentlich-rechtlichen Angelegenheiten legitimiert. Auf die frist- und formgerecht eingereichte Beschwerde ist grundsätzlich - unter Vorbehalt von E. 1.3 hiernach - einzutreten (Art. 42 und Art. 100 BGG).
Die Beschwerde ist im vereinfachten Verfahren gemäss <ref-law> zu behandeln. Das rechtfertigt es auch, redaktionell auf die ansonsten gebotene Trennung zwischen Staats- und Gemeindesteuer bzw. direkter Bundessteuer zu verzichten.
1.3. Gemäss Art. 42 Abs. 1 und 2 BGG haben Rechtsschriften unter anderem die Begehren und deren Begründung zu enthalten; in der Begründung ist in gedrängter Form darzulegen, inwiefern der angefochtene Akt Recht verletzt (vgl. <ref-law>).
1.3.1. Unerlässlich ist namentlich, dass die Beschwerde auf die Begründung des angefochtenen Entscheids eingeht und im Einzelnen aufzeigt, worin Bundesrecht verletzt wird. Die Beschwerdeschrift soll vor Bundesgericht nicht bloss die Rechtsstandpunkte und Argumente wiederholen, wie sie im kantonalen Verfahren vorgebracht worden sind, sondern muss sich konkret und spezifisch mit den als rechtsfehlerhaft erachteten Erwägungen der Vorinstanz auseinandersetzen (vgl. <ref-ruling> E. 2.1 S. 245 f.).
1.3.2. Besonderes gilt hinsichtlich der vorinstanzlichen Sachverhaltsermittlung und Beweiswürdigung. Das Bundesgericht legt seinem Urteil den Sachverhalt zugrunde, wie die Vorinstanz ihn festgestellt hat (<ref-law>). Es kann diesen - soweit entscheidrelevant - berichtigen oder ergänzen, wenn er offensichtlich unrichtig, in Missachtung wesentlicher Verfahrensrechte ermittelt worden ist oder anderweitig auf einer Rechtsverletzung im Sinne von <ref-law> beruht (<ref-law>). Die betroffene Person muss rechtsgenügend dartun, dass und inwiefern der Sachverhalt bzw. die beanstandete Beweiswürdigung klar und eindeutig mangelhaft erscheint (<ref-law>; vgl. <ref-ruling> E. 1.4.3 S.254 f.; <ref-ruling> E. 1.3 S. 251 f.). Rein appellatorische Kritik an der Sachverhaltsermittlung und an der Beweiswürdigung genügt den Begründungs- bzw. Rügeanforderungen nicht (vgl. <ref-ruling> E. 10.1 S. 445 mit Hinweisen).
1.4. Eine diesen strengen Anforderungen genügende Begründung ist hier nur teilweise zu erkennen. Soweit das nicht der Fall ist, kann auf die vorgetragene Kritik nicht eingegangen werden.
2.
2.1. Gemäss <ref-law>, Art. 3 Abs. 1 StHG sowie § 8 Abs. 1 des Steuergesetzes [des Kantons Luzern] vom 22. November 1999 (StG/LU; SRL Nr. 620) sind natürliche Personen aufgrund persönlicher Zugehörigkeit steuerpflichtig, wenn sie ihren steuerrechtlichen Wohnsitz oder Aufenthalt in der Schweiz bzw. im Kanton haben. Einen steuerrechtlichen Wohnsitz in der Schweiz bzw. im Kanton hat eine natürliche Person namentlich, wenn sie sich hier mit der Absicht dauernden Verbleibens aufhält (<ref-law>; Art. 3 Abs. 2 StHG; § 8 Abs. 2 StG/LU; vgl. auch <ref-law>). Der Begriff des steuerrechtlichen Wohnsitzes setzt sich damit aus einem objektiven, äusseren (Aufenthalt) und einem subjektiven, inneren Element (Absicht) zusammen (Urteile 2C_1267/2012 vom 1. Juli 2013 E. 3.1; 2C_627/2011 und 2C_653/2011 vom 7. März 2012 E. 4.1, in: StE 2012 A 31.2 Nr. 10).
2.2. Der steuerrechtliche Wohnsitz einer Person befindet sich dort, wo faktisch der Mittelpunkt ihrer Lebensinteressen liegt ("le lieu où se situe le centre de ses intérêts"; <ref-ruling> E. 3.2 S. 305; <ref-ruling> E. 4.1 S. 36; <ref-ruling> E. 2 S. 56; <ref-ruling> E. 2a S. 293 f.). Dabei ist von objektiven, äusseren Umständen auf innere Tatsachen zu schliessen (vgl. Urteil 2C_92/2012 vom 17. August 2012 E. 4.1, in: StE 2013 A 24.21 Nr. 24). Gemeinhin kann darüber kein klarer Beweis geführt werden, sondern es ist aufgrund von Indizien eine Gewichtung vorzunehmen. Hierzu ist eine sorgfältige Berücksichtigung sämtlicher Berufs-, Familien- und Lebensumstände notwendig (Urteile 2C_793/2013 vom 7. Mai 2014 E. 4.2, in: StE 2014 A 24.21 Nr. 29; 2C_397/2010 vom 6. Dezember 2010 E. 2.4.2, in: StE 2011 A 24.21 Nr. 22). Auf die bloss geäusserten Wünsche der steuerpflichtigen Person oder die gefühlsmässige Bevorzugung eines Ortes kommt es nicht an. Der steuerrechtliche Wohnsitz ist insofern nicht frei wählbar. Gleichermassen spielt das polizeiliche Domizil, an welchem die Schriften hinterlegt sind oder wo die politischen Rechte ausgeübt werden, keine entscheidende Rolle: Als äussere Merkmale können sie ein Indiz für den steuerrechtlichen Wohnsitz bilden, falls auch das übrige Verhalten der Person dafür spricht (<ref-ruling> E. 3.3. S. 306; <ref-ruling> E. 4.1 S. 35 f.).
2.3. Das Bundesgericht hat weiter in konstanter Praxis ausgeführt, dass es für eine Wohnsitzverlegung ins Ausland nicht genügt, die Verbindungen zum bisherigen Wohnsitz zu lösen; entscheidend ist vielmehr, dass nach den gesamten Umständen ein neuer Wohnsitz im Ausland begründet worden ist. Da niemand an mehreren Orten zugleich Wohnsitz haben kann, bleibt der einmal begründete Wohnsitz grundsätzlich bis zum Erwerb eines neuen bestehen (sog. "rémanence du domicile"). Nicht entscheidend ist deshalb, wann sich der Steuerpflichtige am bisherigen Wohnort abgemeldet oder diesen verlassen hat. Begibt er sich ins Ausland, so hat er die direkte Bundessteuer bzw. die Staatssteuer zu entrichten, bis er nachweisbar im Ausland einen neuen Wohnsitz begründet. Eine andere Sichtweise würde eine zu grosse Missbrauchsgefahr nach sich ziehen (<ref-ruling> E. 3.3 S. 306).
2.4. Der Steuerwohnsitz ist als steuerbegründende Tatsache grundsätzlich von den Steuerbehörden nachzuweisen. Der steuerpflichtigen Person kann jedoch der Beweis für die von ihr behauptete Verlagerung des Lebensmittelpunktes an einen neuen Ort auferlegt werden, sofern die von der Steuerbehörde angenommene bisherige subjektive Steuerpflicht als sehr wahrscheinlich erscheint (vgl. Urteil 2C_1267/ 2012 vom 1. Juli 2013 E. 3.4, in: ASA 82 S. 72, mit Hinweisen). Diesfalls ist vom Steuerpflichtigen darzulegen, dass eine Wohnsitzverlegung stattgefunden hat. Dazu gehört nicht nur die endgültige Lösung der Verbindungen zum bisherigen Wohnsitz, sondern auch die Darstellung der Umstände, welche zur Begründung des neuen Wohnsitzes geführt haben (<ref-ruling> E. 3.4 S. 307). Wird der Nachweis der Wohnsitzverlegung nicht erbracht, besteht das bisherige Domizil gemäss dem Gesagten fort (Urteil 2C_1267/2012 vom 1. Juli 2013 E. 3.4, in: ASA 82 S. 72, mit Hinweisen).
3.
3.1. Die Vorinstanz hat die bundesgerichtliche Praxis korrekt dargestellt und dazu festgestellt, die Beschwerdeführer hätten die 4.5-Zimmer-Wohnung in U._ auch nach ihrer Abmeldung am 1. April 2013 nach Portugal nicht gekündigt und während (mindestens) der Hälfte des Jahres 2014 auch benutzt. Zudem verfügten sie immer noch über einen permanenten Telefonanschluss, eine Postadresse sowie zwei auf sie zugelassene Fahrzeuge. Zwar stünde den Beschwerdeführern auch in Portugal ein Haus sowie eine Obstplantage zur Verfügung. Insgesamt hätten aber diese trotz der Aufenthalte in Portugal den Mittelpunkt ihrer Interessen in U._ beibehalten, wo sie ihr gesellschaftliches und geschäftliches Umfeld hätten. Dafür spreche auch der Umstand, dass der Beschwerdeführer 1 Verwaltungsratspräsident mit Einzelunterschrift und die Beschwerdeführerin 2 Verwaltungsrätin mit Kollektivunterschrift der X._ AG sei. Damit seien auch im beruflichen Bereich der Beschwerdeführer die Bande zur Schweiz nicht nachweislich gelockert oder gar gelöst worden. Zudem würden die Beschwerdeführer ihre sozialen Kontakte zu ihrer Familie noch unverändert sorgfältig pflegen und nähmen auch am lokalen Vereinsleben nachweislich teil. Demgegenüber hätten sich die Beschwerdeführer zwar administrativ in Portugal eingerichtet (behördliche Anmeldung, Zuteilung einer Steuernummer und Stimmrechtsausweis als Auslandschweizer). Damit vermöchten die Beschwerdeführer insgesamt nicht nachzuweisen, dass sie ihren Lebensmittelpunkt von der Schweiz nach Portugal verlegt hätten, weshalb das bisherige Domizil fortbestehe.
3.2. Die Beschwerdeführer rügen einzig eine willkürliche Beweiswürdigung sowie eine Verletzung des rechtlichen Gehörs durch die Vorinstanz.
3.2.1. Sie führen aus, der Beschwerdeführer 1 habe 1994 einen schweren Autounfall erlitten, wovon er sich nie gänzlich habe erholen können. Insbesondere weil das Klima in Portugal seine Genesung positiv beeinflusse, hätten sie sich entschieden, ihren Lebensmittelpunkt allmählich nach Portugal zu verlegen. Die Vorinstanz sei auf diesen Einwand nicht eingegangen und habe damit das rechtliche Gehör verletzt. Sodann habe die Vorinstanz von Anfang an einseitig zu Gunsten eines Wohnsitzes in der Schweiz argumentiert; es habe keine eingehende Auseinandersetzung mit den Argumenten der Beschwerdeführer stattgefunden, was wiederum eine Verletzung des rechtlichen Gehörs darstelle.
3.2.2. Der Anspruch auf rechtliches Gehör nach <ref-law> gebietet, dass die Behörde die Vorbringen der betroffenen Person auch tatsächlich hört, prüft und in der Entscheidfindung berücksichtigt. Daraus folgt die Verpflichtung der Behörde, ihren Entscheid zu begründen (<ref-ruling> E. 5.1 S. 503 f.). Dabei ist es nicht erforderlich, dass sie sich mit allen Parteistandpunkten einlässlich auseinandersetzt und jedes einzelne Vorbringen ausdrücklich widerlegt. Vielmehr kann sie sich auf die für den Entscheid wesentlichen Punkte beschränken. Die Begründung muss so abgefasst sein, dass sich die betroffene Person über die Tragweite des Entscheids Rechenschaft geben und ihn in voller Kenntnis der Sache an die höhere Instanz weiterziehen kann. In diesem Sinn müssen wenigstens kurz die Überlegungen genannt werden, von denen sich die Behörde hat leiten lassen und auf die sich ihr Entscheid stützt (vgl. <ref-ruling> E. 2.2 S. 84; <ref-ruling> E. 5.2 S. 236 mit Hinweisen).
3.2.3. Die Vorinstanz hat diese Grundsätze eingehalten. Wenn die Vorinstanz einzelne Elemente weniger stark gewichtet hat, als den Beschwerdeführern vorschwebte, liegt darin keine Verletzung des rechtlichen Gehörs. Die behördliche Begründungspflicht soll den Anspruch der Partei auf eine sachbezogene Begründung gewährleisten (vgl. E. 3.2.2 hiervor); ob diese zutrifft, ist als materielle Frage von der Rechtsmittelinstanz zu entscheiden. Die Begründungspflicht ist erfüllt, wenn die Betroffenen die entsprechende Erwägung sachgerecht anfechten können (vgl. <ref-ruling> E. 2.2.1 S. 188); dies ist hier zweifellos der Fall.
3.2.4. Die Vorinstanz hat im angefochtenen Entscheid insgesamt eine sorgfältige Abwägung sämtlicher Berufs-, Familien- und Lebensumstände der Beschwerdeführer vorgenommen. Sie ist dabei zu Recht zum Schluss gekommen, dass der Nachweis einer Wohnsitzverlegung ins Ausland nicht gelungen ist, weshalb das bisherige Domizil in der Schweiz weiter besteht. Dem blossen Umstand, dass das milde Klima in Portugal der Gesundheit des Beschwerdeführers 1 förderlich ist, kommt dabei - angesichts der zahlreichen noch vorhandenen Verbindungen zur Schweiz - keine entscheidende Bedeutung zu (vgl. Urteil 2C_793/2013 vom 7. Mai 2014 E. 6.3, in: StE 2014 A 24.21 Nr. 29).
3.2.5. Im Übrigen ist nicht ersichtlich, inwiefern die vorinstanzliche Beweiswürdigung geradezu willkürlich sein soll.
Willkür liegt nicht bereits dann vor, wenn eine andere Sicht ebenfalls vertretbar oder sogar zutreffender erscheint, sondern nur, wenn sich die vorinstanzliche Beurteilung als offensichtlich unhaltbar erweist, mit der tatsächlichen Situation in klarem Widerspruch steht oder einen unumstrittenen Rechtsgrundsatz krass verletzt bzw. in stossender Weise dem Gerechtigkeitsgedanken zuwiderläuft (<ref-ruling> E. 5.4 S. 148 mit Hinweisen). Auf rein appellatorische Kritik an der Sachverhaltsermittlung und an der Beweiswürdigung geht das Bundesgericht nicht weiter ein (vgl. E. 1.3.2 hiervor). Die Beschwerdeführer wiederholen weitgehend, was sie bereits im kantonalen Verfahren vorgebracht haben; mit den Ausführungen dazu im angefochtenen Entscheid setzen sie sich in verfassungsrechtlicher Hinsicht kaum auseinander. Sie stellen im Wesentlichen ihre Sicht der Dinge jener der Vorinstanz gegenüber, zeigen indessen nicht auf, inwiefern deren Beweiswürdigung willkürlich wäre.
Soweit die Beschwerdeführer darlegen, sie würden in Portugal ein grosses Grundstück mit zahlreichen Bäumen und Pflanzen bewirtschaften, fehlen - wie die Vorinstanz zu Recht festgestellt hat - entsprechende konkrete Nachweise ebenso wie in Bezug auf angebliche persönliche Freundschaften (so etwa die Mitgliedschaft in einer Wandergruppe) in Portugal. Zudem kommt praxisgemäss dem polizeilichen Domizil keine entscheidende Rolle zu (vgl. E. 2.2 hiervor), weshalb sie aus der Anmeldung in Portugal, dem Eintrag ins Stimmregister für Auslandschweizer wie auch der Zuteilung einer Steuernummer nichts zu ihren Gunsten ableiten können. Zudem ergibt sich aus den der Vorinstanz eingereichten Dokumenten kein eindeutiger Nachweis einer Besteuerung im Ausland.
4.
Nach dem Gesagten sind die beiden Verfahren zu vereinigen und die Beschwerde ist im vereinfachten Verfahren gemäss <ref-law> abzuweisen. Zur Begründung wird ergänzend auf die Erwägungen im angefochtenen Urteil verwiesen (<ref-law>).
Bei diesem Ausgang des Verfahrens werden die Beschwerdeführer unter solidarischer Haftung kostenpflichtig (vgl. Art. 65 f. BGG). Es ist keine Parteientschädigung geschuldet (<ref-law>).

Demnach erkennt das Bundesgericht:
1.
Die Verfahren 2C_510/2016 und 2C_511/2016 werden vereinigt.
2.
Die Beschwerde betreffend die direkte Bundessteuer (2C_511/2016) wird abgewiesen.
3.
Die Beschwerde betreffend die Staats- und Gemeindesteuern (2C_510/2016) wird abgewiesen.
4.
Die Gerichtskosten von insgesamt Fr. 2'000.-- werden den Beschwerdeführern unter solidarischer Haftung auferlegt.
5.
Dieses Urteil wird den Verfahrensbeteiligten, dem Kantonsgericht Luzern, 4. Abteilung, und der Eidgenössischen Steuerverwaltung schriftlich mitgeteilt.
Lausanne, 29. August 2016
Im Namen der II. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Seiler
Der Gerichtsschreiber: Winiger