Also, why am I getting a feeling that a Roman province is different from what we percept as a province (i.e, a part of a country which is heavily integrated into it)? It looks as if in the East they were more like random kingdoms being kept together by Roman legions or something. Protection and whatnot.
Roman provinces are quite complicated beasts, but I'll try and give a rough idea of how they worked. This is going to be a long one.
The first thing you have to bear in mind is that the Romans did not, legally and ideologically, subscribe to the same notions of sovereignty and national borders as we do. They considered that they had the right to enforce their authority across the entire world, and that they chose to actually govern a subset of that. Provinces by their very nature were rather ad hoc: the first was Sicily, because it was simply impossible to govern across the Straits of Messina from Rome. You also have to bear in mind that their cartography was rather poor. All of this has the end result that provinces are not uniform and were - until central government took it upon itself to redefine them, as it did on occasion - a relatively disorganised affair.
What actually qualified as a province varied too. Obviously the acid test was whether that land could be effectively governed by one person and his staff, which broadly meant that the more people and the more danger existed within a province, the smaller it was. However, Roman governors couldn't actually
govern in any meaningful sense even if the wanted to (of which more later). So what you usually ended up with in the West was vaguely carved lines on the map corresponding to geographical features - the early provinces of Gaul were 'Gaul beyond the Alps' and 'Gaul before the Alps' - and phases of conquest. In the East, provinces were often inherited from the Hellenistic powers that governed them beforehand, as in Greece, which divided roughly into 'the Greece of the Persian Wars', Epirus and 'everything else', which they named Macedonia. Egypt remained a province in its entirety. A province needed a capital, so a lot of the provinces were named for their capitals (Narbonensis, Tarraconensis and so on) and simply encompassed a chunk of land around them.
Complicating this picture is the client states, which were not called provinces. These were kingdoms which had been given over to Rome whose monarchs were allowed to stay on, sometimes with a change of succession, and operated nominally outside the imperial framework. However, the Romans usually had some level of control over their administration, always including the right to declare war and make peace and often the right to fiddle with their succession, as in Herod's Galilee where the emperor had to ratify it. When the original client king died, the kingdom was often absorbed into the empire as a province: this happened to Judea and the territory of Pergamon, which became the province of Asia. The whole east bank of the Rhine was lined with client states, which raises one of the big problems of historiography - what's the difference between a client state which is notionally independent but in which Rome can exercise its power and a province in which Rome doesn't do much governing?
You then have the whole problem of government, which is what makes defining Roman borders so difficult. It's pretty self-evident that your Roman governor could not meaningfully direct how his province worked; when you give a man charge over an area the size of Egypt and expect him to be responsible for
everything (a governor's power was limited only by the fact that he could be censured if the emperor disapproved of his actions), he's clearly not going to be able to manage it even if he has the mind to. Most governors, particularly in the late Republican period, saw governorship as a chance to indulge in some good old fashioned corruption and make a lot of money. A governor could be served with thousands of petitions in a week - he simply couldn't deal with all of that and control an area the size of a modern European country with transport no faster than a horse and no staff save what he brought with him.
The result was that day-to-day governance was done by local aristocrats. Imperial rule brought the opportunity to compete for prestige by impressing the emperor via the governor. A well-Romanised Spaniard might aspire to the Senate; there are inscriptions dedicated by men with names like 'Granius Silo, son of Elaesus’, where you can see the adoption of Roman customs as it happened. Local aristocrats collected taxes, paid for local festivals and civic duties, particularly in the East, and kept order just as they had done under previous rulers. Families competed for prestige within cities and cities between each other. Pliny wrote to Trajan at one point in despair, because two cities under his governorship were set to bankrupt themselves in trying to outdo each other in public buildings. The end result of this was that Roman government was actually quite incidental in many cases - the vast majority of Romanised provinces barely felt the involvement of the Roman state at all, and in parts of the world it must have been difficult to tell that it existed at all.
It's true that this was ultimately held together by force, but it's not as simple as that. Yes, certain provinces - Britain and Judea in particular - were heavily militarised, but these were the exception rather than the rule. In fact, imperial ideology depended on a sense of solidarity and imagined community, which is directly at odds with the appalling levels of violence that met the Jewish Revolts. Emperors and propagandists frequently appropriated local history, myths and traditions to fit them into the Roman framework. Hadrian rebuilt what was ostensibly the Delian League (the 'Panhellenion' as he called it) but included cities in it that fought on opposite sides of the Peleponnesian War and had not even been considered Greek at the time. Statues of the imperial family were carried through Ephesus on an annual basis along with those of the city's founder and patron deities. In the Aeneid, Octavian's forces are given the moniker of 'the Italians', while Anthony's are 'the barbarians from the Orient' - of course, both were Romans from all over the empire. So when force was used to suppress rebellions, it was presented as being turned against an external enemy. One of the reasons why there are monuments like the Arch of Titus in Rome (commemorating the Jewish Revolt) but not elsewhere was that it was too difficult to make that myth fly among people whose Roman identity was only recently constructed. Violence was actually a sign of a breakdown in the Roman system, and it's telling that the Roman governors never really anticipated a revolt: the people running the place believed their own PR. Of course, it's not really a question of 'truth' and 'illusion', or 'fooling people' - by making this sort of propaganda, they created a quasi-national identity. After a few decades of Roman rule, even in the wilds of Gaul, people were living in grid-planned towns and local aristocrats were sending their sons to learn Latin and have Roman political careers.
You then have the problem of actually plotting the frontier. The client states issue aside, the general ratio of space to governmental apparatus (astronomical) meant that the actual extent of Roman control - as should by now be reasonably obvious - was a bit uncertain. The emperors in Rome certainly didn't know where their borders were. It's often cited that the Rhine and the Danube marked the frontier, but rivers are not natural borders - what rivers are good for is
supplying military forces along a border, but they have to be
behind the fortifications for that to work. Under Hadrian the
limites (border forts) were constructed in Britain, Germany and North Africa, but these were not designed as impermeable boundaries. In most cases their job was only to observe and tax rather than to prevent border traffic. Even where obvious defensive lines exist, it doesn't follow that these were the borders of effective Roman control, just the lines to which they would fall back in the event of an invasion.
So I suppose the best way of conceptualising it is as something like an area of land surrounding a city over which a centrally-appointed governor had legal authority. Whether 'legal authority' is actually useful is a debate for another day.
EDIT: I should really collect these long posts and make another history article from them!