Tabular with p type columns to fill page width

each tabular column has on the left and right a separation of \tabcolsep which must be substract from the column width if you want it to be of the length \linewidth

\documentclass{article}
\parindent=0pt
\begin{document}

\hrulefill

\begin{tabular}{ | p{\dimexpr 0.25\linewidth-2\tabcolsep} |
                   p{\dimexpr 0.25\linewidth-2\tabcolsep} |
                   p{\dimexpr 0.25\linewidth-2\tabcolsep} |
                   p{\dimexpr 0.25\linewidth-2\tabcolsep} | } \hline
foo & bar & baz & foobar \\\hline
\end{tabular}                

\end{document}

However, using tabularx makes more sense:

\documentclass{article}
\usepackage{tabularx}
\parindent=0pt
\begin{document}

\hrulefill

\begin{tabularx}{\linewidth}{ | X | X | X | X | } \hline
foo & bar & baz & foobar \\\hline
\end{tabularx}                

\end{document}

You may be looking for something like the following, which requires loading the tabularx package:

\noindent % needed if the tabularx environment isn't encased in a table environment
\begin{tabularx}{\textwidth}{|*{4}{X|}}
...
\end{tabularx}

In the title of your posting, you mention you want a solution using columns of type p{<some width>}. The X column provided by the tabularx package is essentially a p column; the tabularx package just saves you the tedium of having to calculate the column widths explicitly. :-)

---

Addendum This can be generalized to (a) tables that take up a width of less than 1\textwidth -- just specify the intended width as the first argument of the tabularx environment, either as an absolute width statement (e.g., 10cm) or as a relative width statement (e.g., 0.85\textwidth) -- and (b) tables with unequal column widths. E.g., assume that the first and third columns, and the second and fourth columns in the first example should have equal widths, and that the second/fourth columns should be 50% wider than the first/third columns. This can be set up with the following (at first slightly bewildering) instruction

\begin{tabularx}{\textwidth}{|>{\hsize=0.8\hsize}X| >{\hsize=1.2\hsize}X |
                              >{\hsize=0.8\hsize}X| >{\hsize=1.2\hsize}X |}

Of course, this can be expressed slightly more succinctly as

\begin{tabularx}{\textwidth}{| *{2}{>{\hsize=0.8\hsize}X| >{\hsize=1.2\hsize}X |}}

The point to note is that the sum of the fractions of \hsize must equal the number of columns of type X (in this example, 4).