How does a computer upscale 1024x768 resolution to 1920x1080? Without there being black bars I mean. 1080 isn't any multiple of 768 so is there some sort of data loss?
In essence a image is  a group of point samples (read A pixel is not a little square3). When you transform or scale the image you need to resample it. So what you do, theoretically, is take the point samples and convert them into a continuous function. Then you sample that continuous function and reconstruct a signal. So, there are two or three different phases here.


Converting the samples to a continuous function, (function reconstruction).
(Transforming)
Re-sampling the signal


Note that none of these steps have a fixed form. In practice, when optimized, it's impossible to tell that there are steps. The transformation does not really have to be simple it could be mapping the shape into a spiral etc. 



Image 1: A 1-D signal reconstructed by different filters.

In practice, quite a bit of lore is known about signal reconstruction in the signal processing field. Designing these filters and choosing the right one is a art form on its own. But, in essence, the choice of filter is a tradeoff between blurring and ringing. Of course the algorithm also has other qualities such as how many instructions it takes to implement and how fast and how much memory it needs etc. Which can be very important in realtime or embedded applications.



Image 2: Overview of entire process.