Q:

Should one always check, if the new operator worked?

I have two questions about the new operator:

Can the new operator fail to allocate memory?  
Should one test after every use of new, if there really was an object created?   

A:

operator new throws a std::bad_alloc exception on failure, unless you're explicitly using the nothrow version. Therefore, don't check the return value: If you arrive at the next line after the constructor call, you can safely assume that the constructor succeeded. 
But do wrap the appropriately-scoped branch of your code in a try-catch block: Usually not right directly around the new call, but somewhere up the line where you can call off everything that depends on the allocation, and nothing else. 
UPDATE: But see also Jonathan Leffler's comment below about the nothrow variant of new. 

A:

Yes, new can fail to allocate memory, but by default it throws an exception when it does fail.
You only need to check the result if you use the no-throw variant of new.

A:

No need to check for null, in general.  An allocation failure will throw a std::bad_alloc exception, which you can deal with if you like.
The standard indicates:
"If an allocation function declared with a non-throwing exception-specification (15.4) fails to allocate storage, it shall return a null pointer. Any other allocation function that fails to allocate storage shall indicate failure only by throwing an exception of a type that would match a handler (15.3) of type std::bad_alloc (18.6.2.1)."

http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2010/n3092.pdf

YMMV depending on how standards-compliant your compiler actually is.  I think most modern c++ compilers should be embarrassed to do it differently. :)

