Will a LED strip be less bright when I drive my mosfets with 3.3V instead of 5V?
They probably will, in my opinion, but there is no guaranteed with such a MOSFET. The key number is the guarantee of Rds(on) at the lowest gate voltage shown in the "Specifications" section. Vgs(th) is the guarantee that the MOSFET will be almost entirely off (250uA). There is a region between Vgs(th) and your operating point and  you want the voltage across the MOSFET to be small or it may get too hot and your LEDs may not be at full brightness. 



In this case, the Rds(on) is guaranteed to be less than 0.039 ohms at 25 degees C Tj with 4.0V Vgs. The transfer characteristics curve is only a typical characteristic and is not guaranteed so it is bad engineering to use it for your particular purpose. It may be appropriate for a hobby project to give it a try, of course.