It took me quite a few months, but I think I've mostly got it now. (I haven't checked the C# specs though, and may be wrong on a few points)
Basically, they're just metadata you can tie to a class or method. A few attributes are "special", and are interpreted by the compiler to make fun things happen. One example is ObsoleteAttribute (use it by specifying [Obsolete("insert message here")] just above a class or method definition) When the compiler sees this, it marks the class as obsolete, and every time it's used, a compiler warning is generated with the message you specified. There's another attribute specifying that all access to a method must be synchronized, to avoid problems with multithreading in nonthread-safe code.
More generally though, they're just "labels" you can stick on pieces of your code. The compiler doesn't do anything with them, it just sticks them into the compiled MSIL code. Using System.Reflection you can retrieve these at runtime and... do with them what you like. You might use attributes to specify which database table a given class corresponds to if you're writing an ORM mapper, or... well whatever you like. Yes, they are kinda elusive, but essentially, just a way to attach various metadata to your classes or methods.