What is aspect-oriented programming?

I understand object oriented programming, and have been writing OO programs for a long time. People seem to talk about aspect-oriented programming, but I've never really learned what it is or how to use it. What is the basic paradigm?

This question is related, but doesn't quite ask it:

Aspect-Oriented Programming vs. Object Oriented Programming

AOP addresses the problem of cross-cutting concerns, which would be any kind of code that is repeated in different methods and can't normally be completely refactored into its own module, like with logging or verification. So, with AOP you can leave that stuff out of the main code and define it vertically like so:

function mainProgram()
{ 
   var x =  foo();
   doSomethingWith(x);
   return x;
}

aspect logging
{ 
    before (mainProgram is called):
    { 
       log.Write("entering mainProgram");
    }

    after (mainProgram is called):
    { 
       log.Write(  "exiting mainProgram with return value of "
                  + mainProgram.returnValue);
    }
 } 

aspect verification
{ 
    before (doSomethingWith is called):
    { 
       if (doSomethingWith.arguments[0] == null) 
       { 
          throw NullArgumentException();
       }

       if (!doSomethingWith.caller.isAuthenticated)
       { 
          throw Securityexception();
       }
    }
 }

And then an aspect-weaver is used to compile the code into this:

function mainProgram()
{ 
   log.Write("entering mainProgram");

   var x = foo();   

   if (x == null) throw NullArgumentException();
   if (!mainProgramIsAuthenticated()) throw Securityexception();
   doSomethingWith(x);   

   log.Write("exiting mainProgram with return value of "+ x);
   return x;
}