The Idea is to head to Mecca.
I will tell you how I did my calculations one day when I was in desert with my friends and we had no one around from the local people who knows the directions in this place. and it worked with me with enough accuracy to make my pray accepted.
to apply this approach you need the most basic primitive tools
you must know the location of Mecca on the world map (fixed information).
you must know your current location on the world map(changing information)
a way to locate the the Cardinal direction (compass) / (or the sun / stars- in case you get lost on an island in a plane crash having no tools)
to imagine the world map in your head and to be aware of some basic geographies
Here are the steps on this example as in this picture:
giving that your position in red and the Qibla in green.
Here are the steps you are going to do on a paper or in your mind -in case of the no-tools island situation-.
step1- locate your position on map. (the red point on the picture)
step2- locate Mecca on map (the green point on the picture) and don't worry it will not change it's location on the map any day.
step3- estimating the angle/degree
If there is an inaccuracy in this method , it will be because of this step , so be accurate as much as you can to get better results. Now we need to estimate the angle/degree of Mecca from our position.
First: draw the 4 Cardinal direction North/South/East/West with your location as the center( as I did in the picture in Blue color) whether on the paper or in your mind.
Second: draw the second angle side/line starting from your position to Mecca (as I did in the picture in the orange color)
third: Now you have your angle , that is between the orange line and the "closest" blue line of the 4 lines(N/S/E/W) in our case the orange line is closer to the East direction (the reason for choosing the closest direction is to generate the smallest angle ,and the smaller the angle is, the more accuracy you get by your estimation)
forth: having our angle we need to measure it's degree , and to do that you need the angle to be drown on a paper and to use a protractor, but as we have no tools we have no way to measure the angle accurately , so we need to estimate it
forgive me for my bad painting. this is how how you can estimate the angle in your mind , knowing that a complete circle is 360 degree , half circle is 180 degrees, a quarter is 90 degrees , half quarter is 45 degrees quarter of quarter is 22.5 degrees. so by looking back to our orange angle in the map on paper or in our head you can estimate the degree, in our example it is about to 30 degrees south east , for more information about naming the angles give this a look.
Now we have what we want - the angle - , it is 30 degrees South the Eaet , let us go for the next step
step 4 (final step): Where is the Qibla?
Now we know that the Qibla is 30 degrees south(or bellow) the East, So we must know where is the "East"! , and to know where is the east you need a campass or in case of the no-tools situation you have to learn how to locate the Directions using the sun or using the stars.
once you know the 4 directions(North - South - East - West) where are they from your location , using whither a compass, the sun or the stars, you have to locate the Qibla! , it is -in our example- 30 degrees south/down the East.
suppose we get the directions using a compass, as in this picture the compass red arm refer to the current North
here is our Qibla , see the Kaaba in the picture? forgive me for the bad painting and shaking hand.
also take a look on the same question on wikihow (Find-the-Qibla-for-Prayer)
Or, you can just throw all of that away and use the other and most accurate Approach you can use for locating the Qibla when you are in new places
ask someone ,"where is the Qibla?"