I'm just trying out Arduino Uno for the first time with 2 blinking LEDs on a breadboard. All the tutorials on the Internet seem to use a resistor. I do know the function of resistors, but does it really matter here? These LEDs are working just fine without a resistor.
Naughty! :-). If they say to use a resistor there's a good reason for that! Switch it off, NOW! 

The resistor is there to limit the LED's current. If you omit it the current limiting has to come from the Arduino's output, and it will not like it. How do you find out what the resistor needs to be? You do know Ohm's Law? If you don't, write it down in big letters:  

\$ V = I \cdot R \$

Voltage equals current times resistance. Or you could say  

\$ R = \dfrac{V}{I} \$

It's the same thing. The voltage you know: Arduino runs at 5V. But not all that will go over the resistor. The LED also has a voltage drop, typically around 2V for a red LED. So there remains 3V for the resistor. A typical indicator LED will have a nominal current of 20mA, then

\$ R = \dfrac{5V - 2V}{20mA} = 150\Omega \$

The Arduino Uno uses the ATmega328 microcontroller. The datasheet says that the current for any I/O pin shouldn't exceed 40mA, what's commonly known as Absolute Maximum Ratings. Since you don't have anything to limit the current there's only the (low!) resistance of the output transistor. The current may so well be higher than 40mA, and your microcontroller will suffer damage.

edit
The following graph from the ATmega's datasheet shows what will happen if you drive the LED without current limiting resistor:  

  

Without load the output voltage is 5V as expected. But the higher the current drawn the lower that output voltage will be, it will drop about 100mV for every extra 4mA load. That's an internal resistance of 25\$\Omega\$. Then  

\$ I = \dfrac{5V - 2V}{25\Omega} = 120mA \$  

The graph doesn't go that far, the resistance will rise with temperature, but the current will remain very high. Remember that the datasheet gave 40mA as Absolute Maximum Rating. You have three times that. This will definitely damage the I/O port if you do this for a long time. And probably the LED as well. A 20mA indicator LED will often have 30mA as Absolute Maximum Rating.
