The rules for writing Skaldic poetry are many and complex. I will try to summarize.

Skaldic poetry is made up of lines of twelve syllables, always referred to as two half lines of six syllables. The first of this pair is called an odd half line and the second an even half line.

The most common unit of Skaldic poetry is the strophe, or stanza, of four lines or eight half lines.

Sentence structure is independent of line structure.

Each half line has three stresses. The fifth syllable is always stressed and the sixth is always unstressed. The first syllable of the second half-line is always stressed. Often, all odd numbered syllables are stressed.

Alliteration, in this context, means "same leading consonant sound" or "any leading vowel". Each line must have three stressed alliterative syllables, two in the first half line and the third as the first syllable of the second half line. Note that I said "alliterative syllables" rather than "alliterative words".

A full rhyme is a syllable that matches in both vowel and ending consonant, also called a perfect rhyme, or what you and I would consider a normal rhyme. A half rhyme is a syllable that matches in either vowel or ending consonant, but not both, also called an imperfect rhyme.

The fifth syllable in each half line must rhyme one of the previous accented syllables in that half line. The first half line must have a half rhyme (NOT a full rhyme) and the second half line must have a full rhyme.

Alliteration and rhyme do not interact. The presence of one neither necessitates nor forbids the presence of the other.

Strophes were informally composed and recited singly or in pairs, but more formal occasions demanded the long lay, or drapa form. This consists of twenty or more strophes, partitioned into three or more parts by a chorus of one, two or four lines which ended a strophe or stood alone.

Skaldic poetry often used a figurative metaphor known as a kenning. For example, "steed of the waves" is a kenning for "ship", and "whales' road" means "ocean". In some drapas, kennings are all-pervasive and no thing is directly named. Kennings can be nested arbitrarily deep, so after turning "ocean" into "whales' road" your would transform each of whale and road into some other obscure phrase, and so on.

Some examples of decoding kennings from vikinganswerlady.org :

"Tree of Thrud of hostilities" means "warrior"

Tree of Thrud of hostilities
Thrud was Thor's daughter, but here the name is used to mean simply goddess, giving
Tree of goddess of hostilities
goddess of hostilities is a kenning for Valkyrie, giving
Tree of the Valkyrie
which means warrior

"Chariot-Vidur of wondrous-wide ground of Endil" means "captain"

Chariot-Vidur of wondrous-wide ground of Endil
Endil is the name of a legendary sea-king. "The sea-king's ground" therefore is the ocean, giving
Chariot-Vidur of the ocean
or
Vidur of the chariot of the ocean
"Chariot of the ocean" is a ship, giving
Vidur of the ship
Vidur is one of the heiti or alternate names of Odin, and here is used to mean god, giving
God of the ship
which is its captain

Here is my first ever attempt at a single such line :

Poems pall when Skaldic
pinch wee brains with detail

Which, I'm sure you noticed, has a full rhyme in the first line rather than a half rhyme, and therefore must be "considered a grave fault"; but I was in a hurry.

A better example, stolen from lojban.org is
 
Sing with me a song of
    soaring birds and words that
tell of hawks; the hall of
    heaven flows with prose of
owls and airborne furless
    awful bats with hats on.
Night and day are not the
    nicest times for rhymes' sound.


I wish I could cite my primary source, but this write-up was made from an email I sent in 1996, which in turn was based on some book belonging to my ex-wife. This write-up was also assisted by
http://www.vikinganswerlady.org/meters.htm
and
http://www.lojban.org/wiki/index.php/Old%20Norse%20verse%20forms