A core province is a province that is considered a rightful part of your realm. Unfortunately, several nations can have a given province as their core, often resulting in wars over the ownership.
Effects of cores
Having cores on provinces outside your realm will give you a casus belli on the country owning the province. Obviously this also means that other countries with cores on provinces in your realm will have a casus belli on you. Core provinces generates an extra 90% of the direct tax paid at the end of each year. Non-core provinces will have a nationalism effect for 30 years after their capture. Nationalism initially causes 9% revolt risk, which decreases linearly to 0 over the 30 years. If a provinces is captured by rebels, 10 years of "extra" nationalism are added.
How to spot a core
You can check which countries have core claims on a province by clicking the province and checking the bottom-right part of the province interface. Little shields show the countries with a core claim on this province. Often there will be only one country with a core and thus only one shield, but it can be more. In example: the province Béarn in southern France is considered a core of Foix, France, and Armagnac in 1453.
Another way of checking cores is through the diplomatic map mode; the map will show the selected country as bright green and cores outside the country's borders with bright green stripes. Provinces inside the realm that are not cores are shown as green with grey stripes. You'll be able to see the difference.
How to gain a core
Typically the provinces that a country own at startup is also its cores, while some nations have additional claims outside their borders. During the game additional cores can be gained, either through events, by occupying a province continuously for 25 years (NA and earlier) or 50 years (IN and later), or by the spy action Fabricate Claims (EU3 and NA). Several events, most notably "Boundary Dispute" and "Claims on our Rivals," grant cores on neighboring provinces. Unification decisions like "Form Russian Nation" generally grant cores on a wide range of territory.
How to lose a core
A country can lose a core claim on a province that is outside its borders. This can happen as part of a peace negotiation following a lost war, or automatically if the country has not tried to capture (going to war with the country that controls the province or having them as a vassal) the province for 50 years. You will, however, not lose cores on same-culture-group provinces outside of your realm this way. For example, if Brandenburg has a core in Holland, it won't lose the core after 50 years, since even though Holland and Brandenburg have different cultures (Dutch and Saxon, respectively), they are both in the Germanic culture group.