How to add an extra level of sections with headings below \subsubsection

You can use the titlesec package to change the way \paragraph formats the titles and set the secnumdepth counter to four to obtain numbering for the paragraphs:

\documentclass{article}
\usepackage{titlesec}

\setcounter{secnumdepth}{4}

\titleformat{\paragraph}
{\normalfont\normalsize\bfseries}{\theparagraph}{1em}{}
\titlespacing*{\paragraph}
{0pt}{3.25ex plus 1ex minus .2ex}{1.5ex plus .2ex}

\begin{document}

\section{Test Section}
test
\subsection{Test Subsection}
test
\subsubsection{Test Subsubsection}
test
\paragraph{Test Modified Paragraph}
test

\end{document}

If you want to define a new sectioning command, you can take a look at Defining custom sectioning commands.

If you want to define a fresh new sectional unit below \subsubsection, but above \paragraph, then you will have to do considerably more work: a new counter has to be created and its representation has to be appropriately defined; the sectional units \paragraph and \subparagraph will also have to be redefined, as well as they corresponding \l@... commands (controlling how the will be typeset in the ToC if the tocdepth value is increased); also, the toclevel (for eventual bookmarks) will have to be considered.

Here's an example showing how to obtain this new sectional unit giving you now the option to use \part, \section, \subsection, \subsubsection, \subsubsubsection, \paragraph, and \subparagraph:

\documentclass{article}
\usepackage{titlesec}
\usepackage{hyperref}

\titleclass{\subsubsubsection}{straight}[\subsection]

\newcounter{subsubsubsection}[subsubsection]
\renewcommand\thesubsubsubsection{\thesubsubsection.\arabic{subsubsubsection}}
\renewcommand\theparagraph{\thesubsubsubsection.\arabic{paragraph}} % optional; useful if paragraphs are to be numbered

\titleformat{\subsubsubsection}
  {\normalfont\normalsize\bfseries}{\thesubsubsubsection}{1em}{}
\titlespacing*{\subsubsubsection}
{0pt}{3.25ex plus 1ex minus .2ex}{1.5ex plus .2ex}

\makeatletter
\renewcommand\paragraph{\@startsection{paragraph}{5}{\z@}%
  {3.25ex \@plus1ex \@minus.2ex}%
  {-1em}%
  {\normalfont\normalsize\bfseries}}
\renewcommand\subparagraph{\@startsection{subparagraph}{6}{\parindent}%
  {3.25ex \@plus1ex \@minus .2ex}%
  {-1em}%
  {\normalfont\normalsize\bfseries}}
\def\toclevel@subsubsubsection{4}
\def\toclevel@paragraph{5}
\def\toclevel@paragraph{6}
\def\l@subsubsubsection{\@dottedtocline{4}{7em}{4em}}
\def\l@paragraph{\@dottedtocline{5}{10em}{5em}}
\def\l@subparagraph{\@dottedtocline{6}{14em}{6em}}
\makeatother

\setcounter{secnumdepth}{4}
\setcounter{tocdepth}{4}

\begin{document}

\tableofcontents
\section{Test Section}
test
\subsection{Test Subsection}
test
\subsubsection{Test Subsubsection}
test
\subsubsubsection{Test Subsubsubsection}
test
\paragraph{Test Paragraph}
test
\subparagraph{Test Subparagraph}
test

\end{document}

Here's a solution that doesn't require the use of a specialized package such as titlesec or sectsty. (There's nothing wrong per se, obviously, with using packages to achieve a certain goal; nevertheless, I think it can be instructive at times to see how one can manipulate some of LaTeX's built-in commands directly.)

If you use the article document class, the default appearance of the output of the commands \subsubsection and \paragraph is set up as follows:

\newcommand\subsubsection{\@startsection{subsubsection}{3}{\z@}%
                {-3.25ex\@plus -1ex \@minus -.2ex}%
                {1.5ex \@plus .2ex}%
                {\normalfont\normalsize\bfseries}}
\newcommand\paragraph{\@startsection{paragraph}{4}{\z@}%
                {3.25ex \@plus1ex \@minus.2ex}%
                {-1em}%
                {\normalfont\normalsize\bfseries}}

To make the \paragraph command behave more like the \subsubsection command, but with less vertical spacing above and below the sectioning header line(s), you could modify the \paragraph command to make its output behave as if it were a "subsubsubsection". The following MWE illustrates a possible setup.

\documentclass{article}
\makeatletter
\renewcommand\paragraph{\@startsection{paragraph}{4}{\z@}%
            {-2.5ex\@plus -1ex \@minus -.25ex}%
            {1.25ex \@plus .25ex}%
            {\normalfont\normalsize\bfseries}}
\makeatother
\setcounter{secnumdepth}{4} % how many sectioning levels to assign numbers to
\setcounter{tocdepth}{4}    % how many sectioning levels to show in ToC

\begin{document}
\tableofcontents
\section{A}
\subsection{B}
\subsubsection{C1}
\paragraph{D1}
\paragraph{D2}
\subsubsection{C2}
\end{document}

I know this is an old question, but I found it with Google and I think the solutions are too complicated.

For me this is the easiest way for a subsubsubsection:

\newcommand{\subsubsubsection}[1]{\paragraph{#1}\mbox{}\\}
\setcounter{secnumdepth}{4}
\setcounter{tocdepth}{4}

After this it's possible to use

\subsubsubsection{Navigator}